結果

問題 No.483 マッチ並べ
コンテスト
ユーザー yuppe19 😺
提出日時 2017-02-16 19:47:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,501 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 51,864 KB
最終ジャッジ日時 2024-11-14 19:58:43
合計ジャッジ時間 1,040 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:9:3: error: ‘vector’ does not name a type
    9 |   vector<vector<int>> fG, rG;
      |   ^~~~~~
main.cpp:10:3: error: ‘vector’ does not name a type
   10 |   vector<bool> used;
      |   ^~~~~~
main.cpp:11:3: error: ‘vector’ does not name a type
   11 |   vector<int> order; // 属する強連結成分のトポロジカル順序
      |   ^~~~~~
main.cpp:12:3: error: ‘vector’ does not name a type
   12 |   vector<int> vertices; // 帰りがけ順の並び
      |   ^~~~~~
main.cpp:19:3: error: ‘vector’ does not name a type
   19 |   vector<int> get_order(); // solve() の後に呼び出してトポロジカル順序を返す。同じ強連結成分は同じ値になる。
      |   ^~~~~~
main.cpp:20:3: error: ‘vector’ does not name a type
   20 |   vector<vector<int>> restore_sccs(); // solve() の後に呼び出して強連結成分をトポロジカル順序で返す
      |   ^~~~~~
main.cpp: In constructor ‘SCC::SCC(int)’:
main.cpp:24:3: error: ‘fG’ was not declared in this scope
   24 |   fG.assign(n, vector<int>());
      |   ^~
main.cpp:24:16: error: ‘vector’ was not declared in this scope
   24 |   fG.assign(n, vector<int>());
      |                ^~~~~~
main.cpp:3:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    2 | #include <algorithm>
  +++ |+#include <vector>
    3 | using namespace std;
main.cpp:24:23: error: expected primary-expression before ‘int’
   24 |   fG.assign(n, vector<int>());
      |                       ^~~
main.cpp:25:3: error: ‘rG’ was not declared in this scope
   25 |   rG.assign(n, vector<int>());
      |   ^~
main.cpp:25:23: error: expected primary-expression before ‘int’
   25 |   rG.assign(n, vector<int>());
      |                       ^~~
main.cpp: In member function ‘void SCC::add_edge(int, int)’:
main.cpp:29:3: error: ‘fG’ was not declared in this scope
   29 |   fG[u].push_back(v);
      |   ^~
mai

ソースコード

diff # 

#include <iostream>
#include <algorithm>
using namespace std;

// 強連結成分 (Strongly Connected Components) 分解
class SCC {
  int n;
  int scc_count; // 強連結成分の個数
  vector<vector<int>> fG, rG;
  vector<bool> used;
  vector<int> order; // 属する強連結成分のトポロジカル順序
  vector<int> vertices; // 帰りがけ順の並び
  void dfs(int u);
  void rdfs(int v, int k);
public:
  SCC(int n); // 頂点数が n のグラフ
  void add_edge(int u, int v); // u から v に辺を張る
  void solve(); // 強連結成分分解する
  vector<int> get_order(); // solve() の後に呼び出してトポロジカル順序を返す。同じ強連結成分は同じ値になる。
  vector<vector<int>> restore_sccs(); // solve() の後に呼び出して強連結成分をトポロジカル順序で返す
};

SCC::SCC(int n) : n(n) {
  fG.assign(n, vector<int>());
  rG.assign(n, vector<int>());
}

void SCC::add_edge(int u, int v) {
  fG[u].push_back(v);
  rG[v].push_back(u);
}

void SCC::dfs(int u) {
  used[u] = true;
  for(int v : fG[u]) {
    if(!used[v]) { dfs(v); }
  }
  vertices.push_back(u);
}

void SCC::rdfs(int v, int k) {
  used[v] = true;
  order[v] = k;
  for(int u : rG[v]) {
    if(!used[u]) { rdfs(u, k); }
  }
}

vector<int> SCC::get_order() {
  return order;
}

void SCC::solve() {
  used.assign(n, false);
  order.assign(n, 0);
  vertices.clear();
  for(int u=0; u<n; ++u) {
    if(!used[u]) { dfs(u); }
  }
  used.assign(n, false);
  scc_count = 0;
  for(int i=vertices.size()-1; i>=0; --i) {
    if(!used[vertices[i]]) { rdfs(vertices[i], scc_count++); }
  }
}

vector<vector<int>> SCC::restore_sccs() {
  vector<vector<int>> res(scc_count, vector<int>()); // res[scc_count][]
  for(int i=0; i<n; ++i) {
    res[order[i]].push_back(i);
  }
  return res;
}

// 2-SAT
class TwoSAT {
  int n;
  SCC g;
public:
  TwoSAT(int n);
  void add_clause(bool flag0, int x0, bool flag1, int x1); // (x0 | x1)という節を追加する
  vector<bool> solve(); // 戻り値: 可能なら真偽の割り当て、不可能なら空配列
};

TwoSAT::TwoSAT(int n) : n(n), g(2*n) {}

void TwoSAT::add_clause(bool flag0, int x0, bool flag1, int x1) {
  g.add_edge(x0 + n * !flag0, x1 + n * flag1); // !x0 => x1
  g.add_edge(x1 + n * !flag1, x0 + n * flag0); // !x1 => x0
  // メモ: (x0 | x1) = (!x0 => x1 & !x1 => x0)
}

vector<bool> TwoSAT::solve() {
  g.solve();
  vector<int> order = g.get_order();
  vector<bool> res(n);
  for(int i=0; i<n; ++i) {
    if(order[i] == order[i+n]) { return vector<bool>(); } // 充足不可能
    if(order[i] > order[i+n])  { res[i] = true; }
  }
  return res;
}

int main(void) {
  int n; scanf("%d", &n);
  vector<int> r0(n), c0(n), r1(n), c1(n);
  for(int i=0; i<n; ++i) {
    scanf("%d%d%d%d", &r0[i], &c0[i], &r1[i], &c1[i]);
  }
  TwoSAT sat(n);
  for(int i=0; i<n; ++i) {
    for(int j=i+1; j<n; ++j) {
      // マッチ棒をそのまま置く(r0,c0 -> r1,c1)ときは true, 
      // 反転させる(r0,c0 <- r1,c1)ときは false.
      // 頭薬が重なるときに節を追加する。
      if(r0[i] == r0[j] && c0[i] == c0[j]) { sat.add_clause(false, i, false, j); }
      if(r1[i] == r0[j] && c1[i] == c0[j]) { sat.add_clause(true,  i, false, j); }
      if(r0[i] == r1[j] && c0[i] == c1[j]) { sat.add_clause(false, i, true,  j); }
      if(r1[i] == r1[j] && c1[i] == c1[j]) { sat.add_clause(true,  i, true,  j); }
    }
  }
  bool able = sat.solve().size();
  puts(able ? "YES" : "NO");
  return 0;
}
0