結果
問題 | No.2301 Namorientation |
ユーザー |
|
提出日時 | 2023-05-12 22:44:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 837 ms / 3,000 ms |
コード長 | 2,961 bytes |
コンパイル時間 | 4,455 ms |
コンパイル使用メモリ | 259,168 KB |
実行使用メモリ | 84,576 KB |
最終ジャッジ日時 | 2024-11-28 19:19:41 |
合計ジャッジ時間 | 24,125 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using vl=vector<long long>; using vvl=vector<vector<long long>>; using vvvl=vector<vector<vector<long long>>>; using pl=pair<long long,long long>; using vpl=vector<pair<long long,long long>>; #define fi first #define se second #define all(x) (x).begin(),(x).end() #define _overload3(_1,_2,_3,name,...) name #define _rep(i,n) repi(i,0,n) #define repi(i,a,b) for(int i=int(a);i<int(b);++i) #define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__) #define pb push_back #define lb lower_bound #define ub upper_bound #include <atcoder/all> using namespace atcoder; using Graph = vector<vector<ll>>; // 探索 vector<bool> seen, finished; // サイクル復元のための情報 int pos = -1; // サイクル中に含まれる頂点 pos stack<ll> hist; // 訪問履歴 long long modpow(long long a, long long n, long long mo){long long res=1;while(n>0){if(n&1){res=res*a%mo;}a=a*a%mo;n>>=1;}return res;} long long Pow(long long a, long long n){long long res=1;while(n>0){if(n&1){res=res*a;}a=a*a;n>>=1;}return res;} const ll MOD=998244353; const ll INF=(1ll<<60); void dfs(const Graph &G, int v, int p) { seen[v] = true; hist.push(v); for (auto nv : G[v]) { if (nv == p) continue; // 逆流を禁止する // 完全終了した頂点はスルー if (finished[nv]) continue; // サイクルを検出 if (seen[nv] && !finished[nv]) { pos = nv; return; } // 再帰的に探索 dfs(G, nv, v); // サイクル検出したならば真っ直ぐに抜けていく if (pos != -1) return; } hist.pop(); finished[v] = true; } int main(){ ll N; cin>>N; vl A(N); vl B(N); rep(i,N) cin>>A[i]>>B[i]; vvl G(N,vl(0)); rep(i,N){ G[A[i]-1].pb(B[i]-1); G[B[i]-1].pb(A[i]-1); } seen.assign(N, false), finished.assign(N, false); pos = -1; dfs(G, 0, -1); set<int> cycle; while (!hist.empty()) { int t = hist.top(); cycle.insert(t); hist.pop(); if (t == pos) break; } ll roo=*begin(cycle); ll roo2=0; set<pl> hen; rep(i,N) hen.insert({A[i]-1,B[i]-1}); for(ll jo:cycle){ if(hen.count({roo,jo})){ roo2=jo; break; } } hen.erase({roo,roo2}); vvl Gs(N,vl(0)); for(pl nue:hen){ Gs[nue.fi].pb(nue.se); Gs[nue.se].pb(nue.fi); } vl oya(N,-1); queue<ll> q; q.push(roo); oya[roo]=roo2; vector<bool> flag(N,false); flag[roo]=true; while(!q.empty()){ ll now=q.front(); q.pop(); for(ll j:Gs[now]){ if(flag[j]) continue; flag[j]=true; oya[j]=now; q.push(j); } } map<pl,ll> m; rep(i,N){ m[{A[i]-1,B[i]-1}]=i; } vl doc(N,0); rep(i,N){ if(i>oya[i]){ doc.at(m.at({min((ll)i,oya[i]),max((ll)i,oya[i])}))=1; } } rep(i,N){ if(doc[i]==0) cout<<"->"<<endl; else cout<<"<-"<<endl; } }