結果
問題 | No.274 The Wall |
ユーザー | monolith |
提出日時 | 2019-03-04 11:28:30 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,725 bytes |
コンパイル時間 | 668 ms |
コンパイル使用メモリ | 77,044 KB |
実行使用メモリ | 137,328 KB |
最終ジャッジ日時 | 2024-06-23 13:21:51 |
合計ジャッジ時間 | 2,744 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
8,704 KB |
testcase_01 | AC | 6 ms
8,704 KB |
testcase_02 | AC | 5 ms
8,704 KB |
testcase_03 | AC | 142 ms
74,308 KB |
testcase_04 | AC | 5 ms
8,704 KB |
testcase_05 | AC | 5 ms
8,644 KB |
testcase_06 | AC | 6 ms
8,704 KB |
testcase_07 | AC | 5 ms
8,576 KB |
testcase_08 | AC | 6 ms
8,704 KB |
testcase_09 | AC | 5 ms
8,808 KB |
testcase_10 | AC | 6 ms
8,448 KB |
testcase_11 | AC | 430 ms
137,328 KB |
testcase_12 | AC | 25 ms
8,772 KB |
testcase_13 | AC | 6 ms
8,768 KB |
testcase_14 | AC | 10 ms
8,832 KB |
testcase_15 | AC | 18 ms
8,776 KB |
testcase_16 | AC | 126 ms
44,544 KB |
testcase_17 | AC | 114 ms
43,844 KB |
testcase_18 | AC | 128 ms
46,848 KB |
testcase_19 | AC | 29 ms
8,960 KB |
testcase_20 | AC | 33 ms
8,900 KB |
testcase_21 | AC | 34 ms
8,704 KB |
testcase_22 | WA | - |
testcase_23 | AC | 35 ms
8,900 KB |
testcase_24 | AC | 35 ms
8,960 KB |
testcase_25 | AC | 35 ms
8,704 KB |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <cstdlib>#include <iostream>#include <cmath>#include <cstring>#include <algorithm>#include <vector>#include <queue>#include <map>using namespace std;typedef pair<long long int, long long int> P;long long int INF = 1e18;long long int MOD = 1e9 + 7;#define MAX_V 110000int V;vector<int> G[MAX_V]; // グラフの隣接リスト表現vector<int> rG[MAX_V];// 辺の向きを逆にしたグラフvector<int> vs; // 帰りがけ順の並びbool used[MAX_V]; // すでに調べたかint cmp[MAX_V]; // 属する強連結成分のトポロジカル順序// from から to への辺を張る関数void add_edge(int from, int to){G[from].push_back(to);rG[to].push_back(from);}void dfs(int v){used[v] = true;for(int i = 0; i < G[v].size(); i++){if(!used[G[v][i]]){dfs(G[v][i]);}}vs.push_back(v);}void rdfs(int v, int k){used[v] = true;cmp[v] = k;for(int i = 0; i < rG[v].size(); i++){if(!used[rG[v][i]]){rdfs(rG[v][i], k);}}}// 強連結成分分解を行う関数、返り値は強連結成分の個数int scc(){memset(used, 0, sizeof(used));vs.clear();for(int v = 0; v < V; v++){if(!used[v]){dfs(v);}}memset(used, 0, sizeof(used));int k = 0;for(int i = vs.size() - 1; i >= 0; i--){if(!used[vs[i]]){rdfs(vs[i], k++);}}return k;}int main(){int N, M;cin >> N >> M;V = N * 2;int L[2100], R[2100];for(int i = 0; i < N; i++){cin >> L[i] >> R[i];}for(int i = 0; i < N; i++){for(int j = i + 1; j < N; j++){if((L[i] <= L[j] && L[j] <= R[i]) || (L[i] <= R[j] && R[j] <= R[i])){add_edge(i, j + N);add_edge(j, i + N);}swap(L[j], R[j]);L[j] = M - L[j] - 1;R[j] = M - R[j] - 1;if((L[i] <= L[j] && L[j] <= R[i]) || (L[i] <= R[j] && R[j] <= R[i])){add_edge(i, j);add_edge(j + N, i + N);}swap(L[j], R[j]);L[j] = M - L[j] - 1;R[j] = M - R[j] - 1;swap(L[i], R[i]);L[i] = M - L[i] - 1;R[i] = M - R[i] - 1;if((L[i] <= L[j] && L[j] <= R[i]) || (L[i] <= R[j] && R[j] <= R[i])){add_edge(i + N, j + N);add_edge(j, i);}swap(L[j], R[j]);L[j] = M - L[j] - 1;R[j] = M - R[j] - 1;if((L[i] <= L[j] && L[j] <= R[i]) || (L[i] <= R[j] && R[j] <= R[i])){add_edge(i + N, j);add_edge(j + N, i);}swap(L[i], R[i]);L[i] = M - L[i] - 1;R[i] = M - R[i] - 1;swap(L[j], R[j]);L[j] = M - L[j] - 1;R[j] = M - R[j] - 1;}}scc();// 同じ強連結成分に属するか判定for(int i = 0; i < N; i++){if(cmp[i] == cmp[i + N]){cout << "NO" << endl;return 0;}}cout << "YES" << endl;return 0;}