結果
問題 |
No.2301 Namorientation
|
ユーザー |
![]() |
提出日時 | 2023-05-12 21:55:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 520 ms / 3,000 ms |
コード長 | 1,841 bytes |
コンパイル時間 | 4,233 ms |
コンパイル使用メモリ | 257,428 KB |
最終ジャッジ日時 | 2025-02-12 22:38:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint998244353 mint; typedef long long ll; int main(){ int n; cin >> n; vector<vector<pair<int,int>>> ikeru; ikeru.resize(n); vector<int> deg(n); vector<int> x(n), y(n); for (int i=0; i<n; i++){ int a, b; cin >> a >> b; a--; b--; deg[a]++; deg[b]++; x[i] = a; y[i] = b; ikeru[a].push_back(pair(b,i)); ikeru[b].push_back(pair(a,i)); } vector<int> mada; vector<bool> isnamori(n, true); vector<int> comefrom(n,-1); vector<int> kousha(n,-1); for (int i=0; i<n; i++){ if (deg[i] == 1){ mada.push_back(i); } } while (!mada.empty()){ int i = mada.back(); mada.pop_back(); isnamori[i] = false; for (auto [j,c]: ikeru[i]){ deg[j]--; if (deg[j] == 1){ mada.push_back(j); }else if (deg[j] <= 0){ kousha[c] = i; } } } vector<bool> tansaku(n); for (int i=0; i<n; i++){ if (!isnamori[i]){ tansaku[i] = true; } } for (int i=0; i<n; i++){ if (isnamori[i]){ mada.push_back(i); break; } } vector<int> arr; while(!mada.empty()){ int i = mada.back(); mada.pop_back(); if (tansaku[i]) continue; arr.push_back(i); tansaku[i] = true; for (auto [j,c]: ikeru[i]){ if (!tansaku[j]){ mada.push_back(j); } } } int m = arr.size(); arr.push_back(arr[0]); for (int i=0; i<m; i++){ comefrom[arr[i+1]] = arr[i]; } for (int i=0; i<n; i++){ if (isnamori[x[i]] && isnamori[y[i]]){ if (comefrom[y[i]] == x[i]){ cout << "->" << endl; }else{ cout << "<-" << endl; } }else if (isnamori[x[i]] && !isnamori[y[i]]){ cout << "<-" << endl; }else if (!isnamori[x[i]] && isnamori[y[i]]){ cout << "->" << endl; }else{ if (kousha[i] == y[i]){ cout << "->" << endl; }else{ cout << "<-" << endl; } } } }