QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#398902 | #8544. Colorful Graph 2 | ucup-team2443# | WA | 68ms | 13424kb | C++14 | 1.0kb | 2024-04-25 19:39:21 | 2024-04-25 19:39:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int d[N],vis[N],ans[N],n,m;
vector<int>e[N],e1[N];
queue<int> q;
void dfs(int u,int c)
{
ans[u]=c;
for(int i=0;i<e1[u].size();i++)
dfs(e1[u][i],c^1);
}
int main()
{
int t,u,v;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
e[i].clear(),e1[i].clear(),d[i]=0,vis[i]=0;
for(int i=0;i<n;i++)
{
e[i].push_back((i+1)%n);
e[(i+1)%n].push_back(i);
d[i]++;d[(i+1)%n]++;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
d[u]++,d[v]++;
}
for(int i=0;i<n;i++)
{
if(d[i]==2)
q.push(i);
}
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=1;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
d[v]--;
if(!vis[v])
e1[v].push_back(u);
if(d[v]==2)
q.push(v);
}
if(q.empty())
dfs(u,0);
}
for(int i=0;i<n;i++)
{
if(ans[i]==1)
printf("R");
else
printf("B");
}
printf("\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13412kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRB BRBB BRBRRB
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 68ms
memory: 13424kb
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:
BRRBRBBRB BRB BRRBB RBBRRB RRRBRBBRB BRB RRBBBRB BRBRBBR BRBB BRBRRB RBRBRB BRBRBBR BBBRBRBR BRB BBRBRRBR BBBRBRBR BRB BRRBRRBRBB BBRRBRBR RBRBBRRBRB RRBBBRRRBB RRBRBBRBRB BRB RRBRBRB RBRBRB RBBBRBRB BRBB RBBBRBR RBBRBRBRBR BRRBRBB BRBRBRBR RBRBRB BRBRRB BRB BRB BBBRBRBRR RBRBBRB BBRRB RBRBRRBBRB BB...
result:
ok ok (100000 test cases)
Test #3:
score: -100
Wrong Answer
time: 64ms
memory: 13192kb
input:
100000 8 4 5 3 5 1 6 1 3 1 7 4 5 0 4 1 4 0 3 1 4 0 8 1 4 7 3 0 3 0 8 1 1 3 3 0 9 4 6 0 3 0 3 1 5 0 7 0 6 2 4 2 0 4 7 3 0 3 0 4 1 3 5 1 3 0 10 4 6 8 5 2 1 5 5 3 5 1 1 4 3 0 9 3 5 0 8 6 6 0 3 0 5 2 1 3 1 4 9 0 6 1 4 2 8 1 1 3 5 0 8 2 3 1 6 1 5 1 3 0 8 3 3 0 7 4 7 5 7 2 5 3 1 3 10 3 8 0 0 3 8 5 9 4 3 0...
output:
BBRBRRBR BBBRRBR RBRB BRBRBRBR BRB BRB BRBBRRBR BRB BBRRRBRBR BRBRBRB RBRBBB RBRBBRB RBRBB RBRBRBRBRB BRBRB BRB BBRBRBRRB BRB RRBBB BRBRBRBRB RBRBBR BRBBRRBR BRBRB BRBRBRBR RBRBB BRBRBBRR RBRRBBR BRBRRBRBRB RRBRBRRBB RBBBBRBRR RBRBRB RBRBRRB BRB BRBBRBRBRB BBRBRR BRBBBRRBR RBRBB RBRRBRRBRB BRRBB BRR...
result:
wrong answer cycle detected (test case 872)