結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
|
提出日時 | 2025-03-14 21:37:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 1,229 bytes |
コンパイル時間 | 6,960 ms |
コンパイル使用メモリ | 332,552 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-14 21:38:05 |
合計ジャッジ時間 | 12,408 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; int main() { int n,m; cin>>n>>m; if(m&1)cout<<-1<<endl,exit(0); vector<int> ans(m); vector<int> e1,en; vector<pair<int,int>> edges(m); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--;v--; edges[i]=make_pair(u,v); if(min(u,v)==0&&max(u,v)==n-1)cout<<-1<<endl,exit(0); if(min(u,v)==0)e1.push_back(i); else if(max(u,v)==n-1)en.push_back(i); } int bcnt=0; dsu uf(n); if(e1.size()*2<=m)for(int x:e1){ ans[x]=1; bcnt++; uf.merge(edges[x].first,edges[x].second); }else for(int x:en){ ans[x]=1; bcnt++; uf.merge(edges[x].first,edges[x].second); } for(int i=0;i<m;i++){ if(ans[i]==1)continue; auto[u,v]=edges[i]; if(bcnt*2==m||(uf.same(0,u)&&uf.same(v,n-1))||(uf.same(0,v)&&uf.same(u,n-1))){ ans[i]=0; }else{ ans[i]=1; uf.merge(u,v); bcnt++; } } for(int i=0;i<m;i++){ if(ans[i]==0)cout<<"R"; else cout<<"B"; } cout<<endl; return 0; }