QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#463782#8544. Colorful Graph 2PhantomThreshold#WA 215ms3660kbC++201.2kb2024-07-05 14:17:272024-07-05 14:17:27

Judging History

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

  • [2024-07-05 14:17:27]
  • 评测
  • 测评结果:WA
  • 用时:215ms
  • 内存:3660kb
  • [2024-07-05 14:17:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		vector<int> deg(n+5);
		vector<set<int>> G(n+5);
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			G[u].insert(v);
			G[v].insert(u);
			deg[u]++;deg[v]++;
		}
		for(int i=0;i<n;i++)
		{
			G[i].insert((i+1)%n);
			G[(i+1)%n].insert(i);
			deg[i]++;deg[(i+1)%n]++;
		}
		vector<int> pre(n+5);
		queue<int> q;
		for(int i=0;i<n;i++)
		{
			if(deg[i]==2)
				q.push(i);
		}
		vector<int> ord;
		while(not q.empty())
		{
			int u=q.front();q.pop();
			ord.push_back(u);
			if(deg[u]!=2)continue;
			int x=*G[u].begin(),y=*next(G[u].begin());
			for(auto z:G[u])
			{
				pre[u]=z;
				deg[z]--;
				G[z].erase(u);
			}
			if(not G[x].contains(y))
			{
				G[x].insert(y);
				G[y].insert(x);
				deg[x]++;deg[y]++;
			}
			if(deg[x]==2)
				q.push(x);
			if(deg[y]==2)
				q.push(y);
		}
		string col(n+5,' ');
		reverse(ord.begin(),ord.end());
		for(auto z:ord)
		{
			if(not pre[z])
				col[z]='R';
			else
				col[z]='R'+'B'-col[pre[z]];
		}
		for(int i=0;i<n;i++)
			cout<<col[i];
		cout<<"\n";
	}
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

BRR
BRBR
RRBBRB

result:

ok ok (3 test cases)

Test #2:

score: 0
Accepted
time: 215ms
memory: 3660kb

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:

BBRBBBRBR
BRR
BBRBR
RRBBRB
RRRBBBRRB
BRR
RRRBRRB
BRBRBRB
BRBR
RRBBRB
RBBRRB
BRBBBRB
BRBRBRRB
BRR
RBRBRRBR
BRBRBRRB
BRR
BRBBRRRRBR
RBBRBBRB
RRRRBBRBRB
BRRBRRBRBR
RRBRBRBRRB
BRR
RRBBRRB
RRRBRB
RBRBRBRB
BRBR
BRBRRBR
BBRRRRBRBR
RRRBBRB
BRBBRRBR
RRRBRB
RRBBRB
BRR
BRR
RBRBRRBRB
RBBBRRB
RBBRB
BBBBBRBRBR
RB...

result:

ok ok (100000 test cases)

Test #3:

score: -100
Wrong Answer
time: 152ms
memory: 3632kb

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:

RRt  tRB
RBRBRBR
BBRR
BBBBRRBR
BRR
BRR
RRBRRBRB
BRR
Rtt  tRRB
BBBBBRR
RRBBRB
R  tRRB
RRBRB
RtR  tBBRB
BRRBR
BRR
RRBRBRtt 
BRR
RRBRB
BBBBBBBRR
RRRBRB
RRBRRBRB
BBBRR
RRRBRBRB
RRBRB
RRBR   t
RRRBBRB
RRBRBRRBRB
BRBRtRBBR
RRBRBRBRB
BBBBRR
BBRRRBR
BRR
RRBRBRBRRB
BRRBRB
RRR t tRB
BBRBR
RRBRRRBRRB
BBRBR
BBR...

result:

wrong answer Token parameter [name=S] equals to "RRt", doesn't correspond to pattern "[BR]{1,200000}" (test case 1)