結果
問題 | No.2301 Namorientation |
ユーザー |
|
提出日時 | 2023-05-13 18:54:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 719 ms / 3,000 ms |
コード長 | 1,427 bytes |
コンパイル時間 | 2,038 ms |
コンパイル使用メモリ | 215,172 KB |
最終ジャッジ日時 | 2025-02-13 00:09:11 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i,n) for (int i=0;i<(int)(n);i++)const int MOD = 998244353;int main(){int n;cin>>n;vector<vector<vector<int>>> g(n);vector<int> ct(n,0);rep(i,n){int a,b;cin>>a>>b;a--; b--;g.at(a).push_back({b,i,0});g.at(b).push_back({a,i,1});ct.at(a)++;ct.at(b)++;}set<int> stl;queue<int> q;rep(i,n) if(ct.at(i)==1){q.push(i);stl.insert(i);}vector<int> ans(n,-1);while(!q.empty()){int nw=q.front();q.pop();vector<int> v={-1,-1,-1};for(auto cv:g.at(nw)){if(stl.count(cv.at(0))) continue;v=cv;break;}if(v.at(0)==-1) continue;ans.at(v.at(1))=v.at(2);ct.at(v.at(0))--;if(ct.at(v.at(0))==1){q.push(v.at(0));stl.insert(v.at(0));}}int st=-1;rep(i,n) if(!stl.count(i)){q.push(i);stl.insert(i);st=i;break;}int ed=-1;while(!q.empty()){int nw=q.front();q.pop();ed=nw;vector<int> v={-1,-1,-1};for(auto cv:g.at(nw)){if(stl.count(cv.at(0))) continue;v=cv;break;}if(v.at(0)==-1) continue;ans.at(v.at(1))=v.at(2);q.push(v.at(0));stl.insert(v.at(0));}for(auto v:g.at(ed)){if(v.at(0)==st){ans.at(v.at(1))=v.at(2);break;}}rep(i,n) cout<<(ans.at(i)?"<-":"->")<<endl;}