QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611152 | #8544. Colorful Graph 2 | ChenJiarun12345 | WA | 0ms | 14220kb | C++14 | 1.3kb | 2024-10-04 19:38:18 | 2024-10-04 19:38:18 |
Judging History
answer
/*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define For(i,l,r) for(register int i=(l);i<=(r);i++)
#define Rof(i,l,r) for(register int i=(l);i>=(r);i--)
#define bug cout<<"Ln:"<<__LINE__<<'\n'
bool MS;
const int N=200005;
int n,m,deg[N],tmp[N],vis[N],col[N],cnt[2];
vector<int>e[N],vec;
void MAIN(int TEST){
cin>>n>>m;
For(i,1,n) e[i].clear(),vis[i]=0;
For(i,1,n) e[i].push_back(i%n+1),e[i%n+1].push_back(i);
For(i,1,m){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
For(i,1,n) deg[i]=(int)e[i].size();
For(i,1,n) if(deg[i]<=2) vec.push_back(i);
Rof(i,n,1){
if(!(int)vec.size()){
cout<<"Impossible\n";
return ;
}
int u=vec.back();
tmp[i]=u,vis[u]=i,vec.pop_back();
for(int v:e[u]) if(!vis[v]){
deg[v]--;
if(deg[v]==2) vec.push_back(v);
}
}
For(i,1,n){
int u=tmp[i];
cnt[0]=0,cnt[1]=0;
for(int v:e[u]) if(vis[v]<vis[u]) cnt[col[v]]++;
if(cnt[0]<=1) col[u]=0;
else col[u]=1;
}
For(i,1,n) cout<<(!col[i]?"B":"R");
cout<<'\n';
}
bool MT;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cerr<<"Memory: "<<1.0*(&MS-&MT)/1048576<<"MiB\n";
int test=1;
cin>>test;
For(TEST,1,test) MAIN(TEST);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 14220kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BBR RBBB BRBBBR
result:
wrong answer cycle detected (test case 2)