結果
問題 | No.274 The Wall |
ユーザー | oyas |
提出日時 | 2017-05-14 09:28:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 392 ms / 2,000 ms |
コード長 | 3,928 bytes |
コンパイル時間 | 964 ms |
コンパイル使用メモリ | 83,760 KB |
実行使用メモリ | 132,224 KB |
最終ジャッジ日時 | 2024-06-22 02:16:28 |
合計ジャッジ時間 | 2,628 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 125 ms
70,016 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 392 ms
132,224 KB |
testcase_12 | AC | 10 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 5 ms
6,940 KB |
testcase_15 | AC | 10 ms
6,940 KB |
testcase_16 | AC | 93 ms
38,784 KB |
testcase_17 | AC | 85 ms
36,992 KB |
testcase_18 | AC | 90 ms
39,936 KB |
testcase_19 | AC | 17 ms
6,944 KB |
testcase_20 | AC | 19 ms
6,944 KB |
testcase_21 | AC | 20 ms
6,940 KB |
testcase_22 | AC | 21 ms
6,944 KB |
testcase_23 | AC | 21 ms
6,940 KB |
testcase_24 | AC | 21 ms
6,940 KB |
testcase_25 | AC | 21 ms
6,940 KB |
ソースコード
// 2sat.cpp#include <vector>#include <iostream>#define rep(i,n) for(int i=0; i<(n); i++)using namespace std;typedef vector<int> vi;// scc.cppのコピー// 強連結成分分解 (Strongly Connected Component)struct SCCGraph: public vector<vi> {vector<int> order; // 属する強連結成分の番号(トポロジカル順序になっている)vector<int> vs; // 帰りがけ順vector<bool> used; // すでに調べたかusing vector::vector; // 継承コンストラクタSCCGraph(const vector<vi> &v): vector::vector(v) {} // コピーコンストラクタを使用可能にする// a -> b の辺を追加する。push_back()でも同じvoid add_edge(int a, int b){(*this)[a].push_back(b);}// scc()で使うvoid dfs(int n, int k, vector<vi> &v, vector<vi> &rv){used[n] = true;order[n] = k;for(auto t: v[n]){if( !rv.empty() ) rv[t].push_back(n); // 逆辺のグラフを作成if( !used[t] ) dfs(t, k, v, rv);}vs.push_back(n);}// 強連結成分分解を行うint scc(){int N = size();used.assign(N, false);order.resize(N);vs.clear();vector<vi> rG(N), tmp; // 辺を逆にしたグラフ用for(int n=0; n < N; n++){if( !used[n] ) dfs(n, n, (*this), rG);}used.assign(N, false);int k = 0; // 強連結成分の番号for(int i = vs.size()-1; i >= 0; i--){if( !used[ vs[i] ] ) dfs(vs[i], k++, rG, tmp);}return k;}// 属する強連結成分が同じかどうか判定bool find(int x, int y){return order[x] == order[y];}};// 関数としてsccを使う。戻り値は、各ノードが所属する強連結成分の番号vector<int> scc(const vector<vi> &v){SCCGraph g(v);g.scc();return g.order;}// 2-SATstruct TwoSAT {SCCGraph graph;int N;TwoSAT(int n): graph( (n+1)*2 ) {N = n;}// 辺( a -> b )を追加する。負の値は論理変数の否定(~a)を表す。void add_edge(int a, int b){if( a < 0 ) a = N - a;if( b < 0 ) b = N - b;graph.add_edge(a, b);}// 論理式( a V b ) を追加する。a,bは、論理変数の番号(0以外の整数)。否定は負の値で表す。void add_or(int a, int b){//if( a < 0 ) a = graph.size() - a;//if( b < 0 ) b = graph.size() - b;//int na = (a + graph.size()) % (2*graph.size());//int nb = (b + graph.size()) % (2*graph.size());add_edge(-a, b);add_edge(-b, a);}// 判定を行うbool solve(){graph.scc();bool ret = true;for(int i=1; i <= N; i++){if( graph.order[i] == graph.order[N+i] ) ret = false;}return ret;}// 変数の値を取得する。bool value(int a){if( a < 0 ) a = N - a;return graph.order[a] > graph.order[(N+a-1)%(2*N)+1];}};// test// yukicoder No.274 The Wall (http://yukicoder.me/problems/no/274)int main(){int N, M;int L[2005], R[2005];int rL[2005], rR[2005];TwoSAT sat(2005);// sat.add_or( 1, -2);// sat.add_or( 2, 3);// sat.add_or(-3, -1);// cout << sat.solve() << endl;// rep(i,3) cout << (sat.value(i+1) ? "true" : "false") << endl;//// return 0;cin >> N >> M;rep(i,N){cin >> L[i] >> R[i];rR[i] = M - L[i] - 1;rL[i] = M - R[i] - 1;//cout << "reverse: " << rL[i] << " " << rR[i] << endl;}//auto fn = [&](int Li, int Lj, int Ri, int Rj, int a, int b){// if( (Lj <= Li && Li <= Rj) ||// (Lj <= Ri && Ri <= Rj) ||// (Li <= Lj && Lj <= Ri) ||// (Li <= Rj && Rj <= Ri) ){// sat.add_or( -a, -b );// }//};auto fn = [&](int Li, int Lj, int Ri, int Rj, int a, int b){if( !(Rj < Li || Ri < Lj) ){sat.add_or( -a, -b );}};rep(i,N) rep(j,i){fn( L[i], L[j], R[i], R[j], (i+1), (j+1) );fn( rL[i], L[j], rR[i], R[j], -(i+1), (j+1) );fn( L[i], rL[j], R[i], rR[j], (i+1), -(j+1) );fn( rL[i], rL[j], rR[i], rR[j], -(i+1), -(j+1) );}cout << (sat.solve() ? "YES" : "NO") << endl;//rep(i,N) cout << sat.value(i+1) << endl;return 0;}