結果
問題 | No.274 The Wall |
ユーザー | monolith |
提出日時 | 2019-03-04 11:28:30 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,725 bytes |
コンパイル時間 | 614 ms |
コンパイル使用メモリ | 77,852 KB |
実行使用メモリ | 137,300 KB |
最終ジャッジ日時 | 2023-09-05 17:53:09 |
合計ジャッジ時間 | 3,034 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
8,720 KB |
testcase_01 | AC | 5 ms
8,596 KB |
testcase_02 | AC | 5 ms
8,644 KB |
testcase_03 | AC | 142 ms
74,104 KB |
testcase_04 | AC | 5 ms
8,644 KB |
testcase_05 | AC | 5 ms
8,608 KB |
testcase_06 | AC | 5 ms
8,784 KB |
testcase_07 | AC | 5 ms
8,636 KB |
testcase_08 | AC | 5 ms
8,712 KB |
testcase_09 | AC | 5 ms
8,936 KB |
testcase_10 | AC | 5 ms
8,664 KB |
testcase_11 | AC | 397 ms
137,300 KB |
testcase_12 | AC | 29 ms
8,696 KB |
testcase_13 | AC | 5 ms
8,728 KB |
testcase_14 | AC | 10 ms
8,756 KB |
testcase_15 | AC | 19 ms
8,760 KB |
testcase_16 | AC | 121 ms
44,496 KB |
testcase_17 | AC | 116 ms
43,768 KB |
testcase_18 | AC | 126 ms
46,812 KB |
testcase_19 | AC | 31 ms
8,840 KB |
testcase_20 | AC | 35 ms
8,956 KB |
testcase_21 | AC | 36 ms
8,844 KB |
testcase_22 | WA | - |
testcase_23 | AC | 38 ms
8,868 KB |
testcase_24 | AC | 38 ms
9,052 KB |
testcase_25 | AC | 39 ms
8,852 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 110000 int 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; }