結果
問題 |
No.2301 Namorientation
|
ユーザー |
![]() |
提出日時 | 2023-05-12 23:01:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 159 ms / 3,000 ms |
コード長 | 2,023 bytes |
コンパイル時間 | 2,137 ms |
コンパイル使用メモリ | 204,812 KB |
最終ジャッジ日時 | 2025-02-12 23:30:47 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<vector<pair<int,int>>>road(N); vector<int>cnt(N); for(int i = 0; i < N; i++) { int A,B; cin >> A >> B; A--; B--; road[A].push_back({B,i+1}); road[B].push_back({A,-i-1}); cnt[A]++; cnt[B]++; } queue<int>que; for(int i = 0; i < N; i++) { if(cnt[i] == 1) { que.push(i); } } vector<int>f(N); while(!que.empty()) { int x = que.front(); que.pop(); for(auto i:road[x]) { cnt[i.first]--; if(cnt[i.first] != 0) { if(i.second < 0) { f[-i.second-1] = 1; } if(cnt[i.first] == 1) { que.push(i.first); } } } } for(int i = 0; i < N; i++) { if(cnt[i] == 2) { que.push(i); while(!que.empty()) { int x = que.front(); que.pop(); cnt[x] = 0; for(auto j:road[x]) { if(cnt[j.first] == 2) { que.push(j.first); if(j.second < 0) { f[-j.second-1] = 1; } break; } } if(que.empty()) { for(auto j:road[x]) { if(j.first == i) { que.push(j.first); if(j.second < 0) { f[-j.second-1] = 1; } } } } } } } for(int i = 0; i < N; i++) { if(f[i]) { cout << "<-" << "\n"; } else { cout << "->" << "\n"; } } }