結果
問題 | No.2301 Namorientation |
ユーザー |
![]() |
提出日時 | 2024-11-08 00:59:01 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 850 ms / 3,000 ms |
コード長 | 1,488 bytes |
コンパイル時間 | 2,690 ms |
コンパイル使用メモリ | 220,216 KB |
実行使用メモリ | 63,704 KB |
最終ジャッジ日時 | 2024-11-08 00:59:26 |
合計ジャッジ時間 | 23,266 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;void fast_io() {ios_base::sync_with_stdio(false);cin.tie(nullptr);}int main() {fast_io();int n;cin >> n;map<pair<int, int>, int> idx;vector<vector<int>> g(n);for (int i = 0; i < n; i++) {int a, b;cin >> a >> b;a--, b--;idx[{a, b}] = i;idx[{b, a}] = i;g[a].push_back(b);g[b].push_back(a);}vector<int> loop;{vector<int> color(n, 0);vector<int> parent(n, -1);function<void(int, int)> dfs = [&](int v, int p) {color[v] = 1;for (int u : g[v]) {if (u == p) {continue;}if (color[u] == 0) {parent[u] = v;dfs(u, v);} else if (color[u] == 1) {int cur = v;while (cur != u) {loop.push_back(cur);cur = parent[cur];}loop.push_back(u);}}color[v] = 2;};dfs(0, -1);}vector<bool> vis(n), ans(n);deque<int> dq;int l = loop.size();for (int i = 0; i < l; i++) {dq.push_back(loop[i]);vis[loop[i]] = 1;int j = loop[i], k = loop[(i + 1) % l];if (j < k) {ans[idx[{j, k}]] = true;} else {ans[idx[{k, j}]] = false;}}while (!dq.empty()) {int v = dq.front();dq.pop_front();for (int u : g[v]) {if (!vis[u]) {vis[u] = 1;dq.push_back(u);if (v < u) {ans[idx[{v, u}]] = false;} else {ans[idx[{u, v}]] = true;}}}}for (int i = 0; i < n; i++) {if (ans[i]) {cout << "->\n";} else {cout << "<-\n";}}}