結果
問題 | No.2301 Namorientation |
ユーザー | AngrySadEight |
提出日時 | 2023-03-16 16:16:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 911 ms / 3,000 ms |
コード長 | 3,590 bytes |
コンパイル時間 | 1,342 ms |
コンパイル使用メモリ | 103,184 KB |
実行使用メモリ | 40,952 KB |
最終ジャッジ日時 | 2023-10-18 13:05:26 |
合計ジャッジ時間 | 21,806 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 1 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 489 ms
22,276 KB |
testcase_13 | AC | 436 ms
20,776 KB |
testcase_14 | AC | 911 ms
35,152 KB |
testcase_15 | AC | 553 ms
24,584 KB |
testcase_16 | AC | 768 ms
30,656 KB |
testcase_17 | AC | 536 ms
23,264 KB |
testcase_18 | AC | 804 ms
31,136 KB |
testcase_19 | AC | 410 ms
19,536 KB |
testcase_20 | AC | 783 ms
30,920 KB |
testcase_21 | AC | 550 ms
24,056 KB |
testcase_22 | AC | 508 ms
40,952 KB |
testcase_23 | AC | 497 ms
40,424 KB |
testcase_24 | AC | 414 ms
34,352 KB |
testcase_25 | AC | 370 ms
28,388 KB |
testcase_26 | AC | 485 ms
36,108 KB |
testcase_27 | AC | 910 ms
35,276 KB |
testcase_28 | AC | 898 ms
35,272 KB |
testcase_29 | AC | 899 ms
35,272 KB |
testcase_30 | AC | 895 ms
35,144 KB |
testcase_31 | AC | 876 ms
35,144 KB |
ソースコード
#include <iostream> #include <vector> #include <utility> #include <map> #include <queue> #include <cassert> using namespace std; int main(){ int N; cin >> N; assert(N >= 3 && N <= 200000); vector<int> A(N); vector<int> B(N); for (int i = 0; i < N; i++){ cin >> A[i] >> B[i]; assert (1 <= A[i] && A[i] < B[i] && B[i] <= N); A[i]--; B[i]--; } map<pair<int,int>, int> mp; for (int i = 0; i < N; i++){ mp[pair<int,int>(A[i], B[i])] = i; } vector<vector<int>> graph(N, vector<int>(0)); for (int i = 0; i < N; i++){ graph[A[i]].push_back(B[i]); graph[B[i]].push_back(A[i]); } vector<bool> tag(N, true); vector<int> count(N, 0); for (int i = 0; i < N; i++){ count[A[i]]++; count[B[i]]++; } //ループ以外の辺を削除するために BFS vector<bool> isvisited(N, false); queue<int> que; for (int i = 0; i < N; i++){ if (count[i] == 1) que.push(i); } while(que.size()){ int p = que.front(); que.pop(); if (isvisited[p]){ continue; } isvisited[p] = true; for (int x: graph[p]){ tag[mp[pair<int,int>(min(p, x), max(p, x))]] = false; count[x]--; if (count[x] == 1){ que.push(x); } } } vector<int> ans(N); // ループのみのグラフ vector<vector<int>> graph2(N, vector<int>(0)); int start = -1; for (int i = 0; i < N; i++){ if (tag[i]){ start = A[i]; graph2[A[i]].push_back(B[i]); graph2[B[i]].push_back(A[i]); } } // ループの中だけをみる for (int i = 0; i < N; i++) isvisited[i] = false; int now = start; while(true){ isvisited[now] = true; bool seen = false; for (int i = 0; i < graph2[now].size(); i++){ if (isvisited[graph2[now][i]]){ continue; } seen = true; if (graph2[now][i] > now){ ans[mp[pair<int,int>(now, graph2[now][i])]] = 1; } else{ ans[mp[pair<int,int>(graph2[now][i], now)]] = 0; } now = graph2[now][i]; break; } if (!seen){ for (int i = 0; i < graph2[now].size(); i++){ if (graph2[now][i] == start){ if (graph2[now][i] > now){ ans[mp[pair<int,int>(now, graph2[now][i])]] = 1; } else{ ans[mp[pair<int,int>(graph2[now][i], now)]] = 0; } } } break; } } // ループの外だけで BFS for (int i = 0; i < N; i++){ if (isvisited[i]){ que.push(i); while(que.size()){ int p = que.front(); que.pop(); for (int x: graph[p]){ if (isvisited[x]) continue; isvisited[x] = true; if (p > x){ ans[mp[pair<int,int>(x, p)]] = 1; } else{ ans[mp[pair<int,int>(p, x)]] = 0; } que.push(x); } } } } for (int i = 0; i < N; i++){ if (ans[i] == 1) cout << "->" << endl; else cout << "<-" << endl; } return 0; }