結果
問題 | No.274 The Wall |
ユーザー | たこし |
提出日時 | 2017-05-15 11:49:19 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,144 bytes |
コンパイル時間 | 1,565 ms |
コンパイル使用メモリ | 159,364 KB |
実行使用メモリ | 132,048 KB |
最終ジャッジ日時 | 2023-10-14 13:11:25 |
合計ジャッジ時間 | 3,834 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,352 KB |
testcase_02 | AC | 1 ms
4,352 KB |
testcase_03 | AC | 113 ms
68,744 KB |
testcase_04 | AC | 1 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,352 KB |
testcase_06 | AC | 1 ms
4,352 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 1 ms
4,352 KB |
testcase_10 | AC | 1 ms
4,352 KB |
testcase_11 | AC | 328 ms
132,048 KB |
testcase_12 | AC | 27 ms
4,352 KB |
testcase_13 | AC | 2 ms
4,348 KB |
testcase_14 | WA | - |
testcase_15 | AC | 18 ms
4,352 KB |
testcase_16 | AC | 174 ms
75,596 KB |
testcase_17 | AC | 158 ms
68,948 KB |
testcase_18 | AC | 171 ms
74,992 KB |
testcase_19 | AC | 32 ms
4,352 KB |
testcase_20 | AC | 35 ms
4,352 KB |
testcase_21 | AC | 40 ms
4,352 KB |
testcase_22 | WA | - |
testcase_23 | AC | 40 ms
4,352 KB |
testcase_24 | WA | - |
testcase_25 | AC | 40 ms
4,352 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double using namespace std; //変数は1-index class SAT_2{ public: SAT_2(int aN) { init(aN); } //変数の数 void init(int aN) { N = aN; VecSize = 2 * N + 1; Edge.resize(VecSize); rEdge.resize(VecSize); used.resize(VecSize); vs.clear(); cmp.resize(VecSize); } //節を登録 void reg(int l, int r) { int tmpL = l, tmpR = r; tmpL *= -1; tmpL += N, tmpR += N; Edge[tmpL].push_back(tmpR); rEdge[tmpR].push_back(tmpL); tmpL = r, tmpR = l; tmpL *= -1; tmpL += N, tmpR += N; Edge[tmpL].push_back(tmpR); rEdge[tmpR].push_back(tmpL); } void dfs(int v) { used[v] = true; for (int i = 0; i < Edge[v].size(); i++) { if(!used[Edge[v][i]]){ dfs(Edge[v][i]); } } vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for (int i = 0; i < rEdge[v].size(); i++) { if(!used[rEdge[v][i]]){ rdfs(rEdge[v][i], k); } } } int scc() { for (int i = 0; i < used.size(); i++) { used[i] = false; } vs.clear(); for (int i = 0; i < VecSize; i++) { if(!used[i]) dfs(i); } for (int i = 0; i < used.size(); i++) { used[i] = false; } int k = 0; for (int i = vs.size()-1; 0 <= i; i--) { if(!used[vs[i]]){ rdfs(vs[i], k++); } } return k; } bool checkSatisfy() { scc(); for(int i = 0; i < N; i++){ if(cmp[i] == cmp[i+N+1]){ return false; } } return true; } private: vector<vector<int>> Edge; vector<vector<int>> rEdge; vector<bool> used; vector<int> vs; //帰りがけ順の並び vector<int> cmp; //属する連結成分のトポロジカル順序 int N; int VecSize; }; #define MAX_N 2005 #define MAX_M 4005 int N, M; int L[MAX_N], R[MAX_N]; //衝突しているか bool checkCollision(int l1, int r1, int l2, int r2) { if(r1 < l1){ swap(l1, r1); } if(r2 < l2){ swap(l2, r2); } if(l1 <= l2 && l2 <= r1){ return true; } if(l1 <= r2 && r2 <= r1){ return true; } return false; } int main() { cin >> N >> M; for (int i = 1; i <= N; i++) { cin >> L[i] >> R[i]; } SAT_2 sat(N); for (int i = 1; i <= N; i++) { for (int j = i+1; j <= N; j++) { if(i == j){ continue; } if(checkCollision(L[i], R[i], L[j], R[j])){ sat.reg(i, j); } if(checkCollision(L[i], R[i], M - 1 - L[j], M - 1 - R[j])){ sat.reg(i, -j); } if(checkCollision(M - 1 - L[i], M - 1 - R[i], L[j], R[j])){ sat.reg(-i, j); } if(checkCollision(M - 1 - L[i], M - 1 - R[i], M - 1 - L[j], M - 1 - R[j])){ sat.reg(-i, -j); } } } if(sat.checkSatisfy()){ cout << "YES" << endl; } else{ cout << "NO" << endl; } return 0; }