QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408851#8544. Colorful Graph 2daduoli#WA 76ms10512kbC++141.4kb2024-05-11 09:21:412024-05-11 09:21:41

Judging History

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

  • [2024-05-11 09:21:41]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:10512kb
  • [2024-05-11 09:21:41]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=2e5+10;
int n,m;
int fs[MAXN],pre[MAXN],suf[MAXN];
vector<int> e[MAXN];
void add(int f,int t) {
	e[f].push_back(t);
}
int sz;
void dfs(int u) {
	++sz;
	for(auto t:e[u]) {
		if(!fs[t]) {
			if(fs[u]==1) fs[t]=2;
			else fs[t]=1;
			dfs(t);
		}
	}
}
void vmain() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) {
		e[i].clear();
		fs[i]=0;
	}
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		++u; ++v;
		add(u,v);
		add(v,u);
	}
	int lr=0,lb=0;
	for(int i=1;i<=n;++i) {
		if(!fs[i]) {
			fs[i]=1; sz=0;
			dfs(i);
			if(sz==1) fs[i]=0;
		}
	}
	if(!m) {
		for(int i=1;i<=n;++i) {
			if((i&1)) printf("R");
			else printf("B");
		}
		puts("");
		return ;
	}
	int pp=0,ss=0;
	for(int i=1;i<=n;++i) {
		if(fs[i]) {
			ss=i;
			break;
		}
	}
	for(int i=n;i>=1;--i) {
		if(fs[i]) {
			pp=i;
			break;
		}
	}
	for(int i=1;i<=n;++i) {
		if(fs[i]) pp=i;
		pre[i]=pp;
	}
	for(int i=n;i>=1;--i) {
		if(fs[i]) ss=i;
		suf[i]=ss;
	}
	for(int i=1;i<=n;++i) {
		if(!fs[i]) {
//			if(i==n) {
//				cout<<pre[i]<<" "<<suf[i]<<endl;
//			}
			if(fs[pre[i]]==fs[suf[i]]) {
				if(fs[pre[i]]==1) fs[i]=2;
				else fs[i]=1;
			}
			else fs[i]=1;
		}
	}
	for(int i=1;i<=n;++i) {
		if(fs[i]==1) printf("R");
		else printf("B");
	} puts("");
}
int main () {
	int T;
	scanf("%d",&T);
	while(T--) vmain();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

RBR
RRRB
RRBRRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 76ms
memory: 9536kb

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:

RRBBBRRBR
RBR
RRBRR
RRRRBB
RRRBBRRRB
RBR
RRRBBRR
RRRBBBR
RRRB
RBRRBR
RRRBRR
RRRRRBR
RRRBBBRR
RBR
RRBBRRBR
RRRBBBRR
RBR
RRBBBBBRRR
RRBRRRBB
RRRRRRRBBB
RRRRRRBBBB
RRBBRRBBRR
RBR
RRBRRRB
RRRBBB
RRBRRRRR
RRRB
RRBBRRR
RRRRRRBBBB
RRRRRBB
RRBRRRBB
RRRBBB
RRBRRB
RBR
RBR
RRRBBRRRB
RRRRBRR
RRRBR
BRRRRBBRRR
RR...

result:

wrong answer cycle detected (test case 47)