結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
![]() |
提出日時 | 2025-03-14 21:27:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 159 ms / 2,000 ms |
コード長 | 973 bytes |
コンパイル時間 | 4,202 ms |
コンパイル使用メモリ | 252,744 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-14 21:27:21 |
合計ジャッジ時間 | 10,620 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000000 #define Inf64 1000000000000000001LL int main(){ int n,m; cin>>n>>m; vector<int> u(m),v(m); int x = 0,y = 0; rep(i,m){ cin>>u[i]>>v[i]; u[i]--,v[i]--; } if(m%2==1){ cout<<"-1"<<endl; return 0; } int R = 0,B = 0; string ans(m,'A'); dsu D0(n),D1(n); rep(i,m){ if(u[i]==0 && v[i]==n-1){ cout<<-1<<endl; return 0; } if(u[i]!=0){ D0.merge(u[i],v[i]); } if(v[i]!=n-1){ D1.merge(u[i],v[i]); } } rep(i,m){ if(u[i]==0){ if(D0.same(n-1,v[i])){ ans[i] = 'R'; R++; } } if(v[i]==n-1){ if(D1.same(u[i],0)){ ans[i] = 'B'; B++; } } } rep(i,m){ if(ans[i]=='A'){ if(R<B){ ans[i] = 'R'; R++; } else{ ans[i]='B'; B++; } } } cout<<ans<<endl; return 0; }