結果
問題 | No.483 マッチ並べ |
ユーザー | kimiyuki |
提出日時 | 2017-04-18 15:36:49 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,992 bytes |
コンパイル時間 | 1,178 ms |
コンパイル使用メモリ | 74,728 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 07:37:17 |
合計ジャッジ時間 | 2,757 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 1 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 1 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 1 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 1 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 1 ms
5,376 KB |
testcase_36 | AC | 1 ms
5,376 KB |
testcase_37 | AC | 1 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 1 ms
5,376 KB |
testcase_40 | AC | 1 ms
5,376 KB |
testcase_41 | AC | 1 ms
5,376 KB |
testcase_42 | AC | 2 ms
5,376 KB |
testcase_43 | AC | 1 ms
5,376 KB |
testcase_44 | AC | 2 ms
5,376 KB |
testcase_45 | AC | 2 ms
5,376 KB |
testcase_46 | AC | 1 ms
5,376 KB |
testcase_47 | AC | 2 ms
5,376 KB |
testcase_48 | AC | 2 ms
5,376 KB |
testcase_49 | AC | 1 ms
5,376 KB |
testcase_50 | AC | 2 ms
5,376 KB |
testcase_51 | AC | 1 ms
5,376 KB |
testcase_52 | AC | 1 ms
5,376 KB |
testcase_53 | AC | 1 ms
5,376 KB |
testcase_54 | AC | 1 ms
5,376 KB |
testcase_55 | AC | 1 ms
5,376 KB |
ソースコード
#include <cstdio> #include <vector> #include <algorithm> #include <tuple> #include <cassert> #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i)) #define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i)) using namespace std; struct strongly_connected_components { static pair<int,vector<int> > decompose(vector<vector<int> > const & g) { // adjacent list strongly_connected_components scc(g); return { scc.k, scc.c }; } private: int n; vector<vector<int> > to, from; explicit strongly_connected_components(vector<vector<int> > const & g) : n(g.size()), to(g), from(n) { repeat (i,n) for (int j : to[i]) from[j].push_back(i); decompose(); } vector<bool> used; vector<int> vs; void dfs(int i) { used[i] = true; for (int j : to[i]) if (not used[j]) dfs(j); vs.push_back(i); } int k; // number of scc vector<int> c; // i-th vertex in g is in c_i-th vertex in scc-decomposed g void rdfs(int i) { used[i] = true; c[i] = k; for (int j : from[i]) if (not used[j]) rdfs(j); } void decompose() { used.clear(); used.resize(n, false); repeat (i,n) if (not used[i]) dfs(i); used.clear(); used.resize(n, false); k = 0; c.resize(n); reverse(vs.begin(), vs.end()); for (int i : vs) if (not used[i]) { rdfs(i); k += 1; } } }; vector<bool> twosat(int n, vector<pair<int, int> > const & cnf) { // make digraph vector<vector<int> > g(2*n); auto i = [&](int x) { assert (x != 0 and abs(x) <= n); return x > 0 ? x-1 : n-x-1; }; for (auto it : cnf) { int x, y; tie(x, y) = it; // x or y g[i(- x)].push_back(i(y)); // not x implies y g[i(- y)].push_back(i(x)); // not y implies x } // do SCC vector<int> component = strongly_connected_components::decompose(g).second; vector<bool> valuation(n); repeat_from (x,1,n+1) { if (component[i(x)] == component[i(- x)]) { // x iff not x return vector<bool>(); // unsat } valuation[x-1] = component[i(x)] > component[i(- x)]; // use components which indices are large } return valuation; } int main() { int n; scanf("%d", &n); vector<int> y[2] = { vector<int>(n), vector<int>(n) }; vector<int> x[2] = { vector<int>(n), vector<int>(n) }; repeat (i,n) scanf("%d%d%d%d", &y[0][i], &x[0][i], &y[1][i], &x[1][i]); vector<pair<int, int> > cnf; repeat (j,n) repeat (i,j) { repeat (p,2) repeat (q,2) { if (make_pair(y[p][i], x[p][i]) == make_pair(y[q][j], x[q][j])) { int vi = (i+1) * (p ? 1 : -1); int vj = (j+1) * (q ? 1 : -1); cnf.emplace_back(- vi, - vj); cnf.emplace_back(- vj, - vi); } } } bool is_sat = not twosat(n, cnf).empty(); printf("%s\n", is_sat ? "YES" : "NO"); return 0; }