結果
問題 | No.1640 簡単な色塗り |
ユーザー |
|
提出日時 | 2021-08-06 21:57:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 1,117 bytes |
コンパイル時間 | 810 ms |
コンパイル使用メモリ | 83,660 KB |
実行使用メモリ | 17,900 KB |
最終ジャッジ日時 | 2024-06-29 15:05:27 |
合計ジャッジ時間 | 17,721 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 TLE * 2 |
コンパイルメッセージ
main.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 26 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>#include<atcoder/dsu>using namespace std;int N;int A[1<<17],B[1<<17];int ans[1<<17];vector<int>E[1<<17];vector<pair<int,int> >G[1<<17];void dfs(int u,int p){for(pair<int,int>e:G[u]){int v=e.first;if(v!=p){ans[e.second]=v;dfs(v,u);}}}void TLE(){for(int i=0;;i++)cout<<i<<endl;}main(){cin>>N;if(N<1||100000<N)TLE();atcoder::dsu P(N);for(int i=0;i<N;i++){cin>>A[i]>>B[i];if(A[i]<1||B[i]<1||N<A[i]||N<B[i])TLE();A[i]--,B[i]--;P.merge(A[i],B[i]);}for(int i=0;i<N;i++){int p=P.leader(A[i]);E[p].push_back(i);}atcoder::dsu Q(N);for(int i=0;i<N;i++)if(i==P.leader(i)){int fi=-1;for(int ei:E[i]){int a=A[ei],b=B[ei];if(Q.same(a,b)){if(fi!=-1){cout<<"No"<<endl;return 0;}fi=ei;}else{G[a].push_back(make_pair(b,ei));G[b].push_back(make_pair(a,ei));Q.merge(a,b);}}if(fi==-1){cout<<"No"<<endl;return 0;}dfs(A[fi],-1);ans[fi]=A[fi];}cout<<"Yes"<<endl;for(int i=0;i<N;i++)cout<<ans[i]+1<<endl;}