QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398902#8544. Colorful Graph 2ucup-team2443#WA 68ms13424kbC++141.0kb2024-04-25 19:39:212024-04-25 19:39:23

Judging History

你现在查看的是最新测评结果

  • [2024-04-25 19:39:23]
  • 评测
  • 测评结果:WA
  • 用时:68ms
  • 内存:13424kb
  • [2024-04-25 19:39:21]
  • 提交

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)