結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
|
提出日時 | 2025-03-14 22:08:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 2,067 bytes |
コンパイル時間 | 3,659 ms |
コンパイル使用メモリ | 288,916 KB |
実行使用メモリ | 18,232 KB |
最終ジャッジ日時 | 2025-03-14 22:08:59 |
合計ジャッジ時間 | 10,106 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<vvl> vvvl; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define rep(i,l,r) for(int i=(l);i<(r);i++) #define all(a) begin(a),end(a) #define sz(a) (int)(a).size() #define F first #define S second template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,0,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;} template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;} template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;} #include<atcoder/dsu> using namespace atcoder; int main(){ int N,M;cin>>N>>M; if(M%2){cout<<-1<<endl;return 0;} vector<pii>A(M); rep(i,0,M)cin>>A[i].F>>A[i].S; rep(i,0,M)A[i].F--,A[i].S--; if(count(all(A),pii(0,N-1))){cout<<-1<<endl;return 0;} vvl E(N); rep(i,0,M)E[A[i].F].emplace_back(A[i].S),E[A[i].S].emplace_back(A[i].F); string ans=string(M,'-'); int R=M/2,B=M/2; if(sz(E[0])<=M/2&&sz(E[N-1])<=M/2){ rep(i,0,M){ if(A[i].F==0)ans[i]='R',R--; if(A[i].S==N-1)ans[i]='B',B--; } rep(i,0,M)if(ans[i]=='-'){ if(R)ans[i]='R',R--; else ans[i]='B'; } } else if(sz(E[0])>M/2){ rep(i,0,M)if(A[i].S==N-1)ans[i]='B',B--; dsu D(N); rep(i,0,M)if(A[i].F)D.merge(A[i].F,A[i].S); assert(D.size(N-1)<=1+M-sz(E[0])); rep(i,0,M)if(A[i].S!=N-1){ if(B){ if(A[i].F==0&&!D.same(A[i].S,N-1))ans[i]='B',B--; else if(A[i].F)ans[i]='B',B--; else ans[i]='R',R--; } else ans[i]='R'; } } else{ rep(i,0,M)if(A[i].F==0)ans[i]='B',B--; dsu D(N); rep(i,0,M)if(A[i].S!=N-1)D.merge(A[i].F,A[i].S); assert(D.size(0)<=1+M-sz(E[N-1])); rep(i,0,M)if(A[i].F){ if(B){ if(A[i].S==N-1&&!D.same(A[i].F,0))ans[i]='B',B--; else if(A[i].S!=N-1)ans[i]='B',B--; else ans[i]='R',R--; } else ans[i]='R'; } } cout<<ans<<endl; }