QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#454692 | #8544. Colorful Graph 2 | ucup-team3678# | WA | 55ms | 12988kb | C++17 | 1.6kb | 2024-06-25 10:08:42 | 2024-06-25 10:08:43 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e5+5;
int T,n,m,tot,U[N],V[N],d[N],ans,c[N];bool v[N],ban[3];
basic_string<int>E[N];
inline void add(int u,int v,int i){d[u]++,d[v]++,U[i]=u,V[i]=v;}
inline void ad(int i,int j,int k)
{
memset(ban,0,sizeof(ban));
if(c[i]!=-1) ban[c[i]]=1;
if(c[j]!=-1) ban[c[j]]=1;
if(c[k]!=-1) ban[c[k]]=1;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
while(T--)
{
cin>>n>>m;tot=0;
for(int i=0;i<n;i++) add(i,(i+1)%n,i+1),c[i]=-1;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,add(u,v,i+n);m+=n;
for(int i=1,u,v;i<=m;i++) u=U[i],v=V[i],(d[u]>d[v]||(d[u]==d[v]&&u>v))&&(swap(u,v),1),E[u]+=v;
for(int i=0;i<n;i++)
{
for(int j:E[i]) v[j]=1;
for(int j:E[i]) for(int k:E[j]) if(v[k])
{
// g[{i,j}].push_back(k);
ad(i,j,k);
if(c[i]==-1)
{
for(int l=0;l<3;l++) if(!ban[l]){c[i]=l;ban[l]=1;break;}
}
if(c[j]==-1)
{
for(int l=0;l<3;l++) if(!ban[l]){c[j]=l;ban[l]=1;break;}
}
if(c[k]==-1)
{
for(int l=0;l<3;l++) if(!ban[l]){c[k]=l;ban[l]=1;break;}
}
// int c[3]={i,j,k};sort(c,c+3);
// g[{c[0],c[1]}].push_back(c[2]);
// g[{c[1],c[2]}]
// cout<<i<<" "<<j<<" "<<k<<'\n';
}
for(int j:E[i]) v[j]=0;
}
for(int i=0;i<n;i++) cout<<((c[i]==0)?'B':'R');cout<<"\n";
// for(int i=0;i<n;i++) cout<<c[i]<<" ";cout<<"\n";
for(int i=0;i<n;i++) E[i].clear(),d[i]=0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12496kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRR BRBR BRRBRR
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 55ms
memory: 12988kb
input:
100000 9 6 2 0 4 6 3 6 0 6 0 7 2 6 3 0 5 2 2 4 2 0 6 3 1 5 4 1 2 4 9 6 3 1 6 4 8 1 3 6 1 6 8 6 3 0 7 4 3 0 4 0 6 4 3 1 7 4 5 1 5 0 3 1 1 4 4 1 1 3 6 3 2 4 4 0 2 0 6 3 3 0 1 3 5 3 7 4 0 5 2 5 5 1 3 5 8 5 4 1 5 1 5 0 1 3 5 7 3 0 8 5 0 2 4 6 0 6 0 3 4 0 8 5 5 1 1 4 5 0 3 1 5 7 3 0 10 7 0 2 9 2 5 8 3 9 ...
output:
RBRRRRBRB BRR BRRBR BRBRRR BRBRRRBRR BRR BRBRRBR BRBRBRR BRBR BRRBRR BRBRBR BRBRBRR BRBRBRBR BRR RBRBRRBR BRBRBRBR BRR BRRBRRRRBR BRBRRRBR BRBRRRBRBR BRBRRRBRRR BRRRBRRRBR BRR BRRRBRR BRBRBR BRRBRBRR BRBR BRRBRRR BRBBRBRRRR BRBRBRR BRBRRBRR BRBRBR BRRBRR BRR BRR BRBRBRRRR BRBRRBR BRBRR BRRRRBRBRR BR...
result:
wrong answer cycle detected (test case 4)