QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#43543	#4243. Good Coloring	crzsty	WA	100ms	8740kb	C++	1.4kb	2022-08-09 18:25:10	2022-08-09 18:25:11

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-08-09 18:25:11]
评测

测评结果：WA
用时：100ms
内存：8740kb

查看

[2022-08-09 18:25:10]
提交

answer

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int M=1e5+10;
int n,m,k;
int c[M],had[M];
vector <int> G[M],C[M];
void dfs(int a){
	if(c[a]==1){
		printf("%d ",a);
		return;
	}
	for(int u:G[a]){
		if(c[u]==c[a]-1){
			dfs(u);
			break;
		}
	}
	printf("%d ",a);
}
void bfs(int x){
	queue <int> Q;
	Q.push(x);
	c[x]=1;
	while(!Q.empty()){
		int a=Q.front();Q.pop();
		had[a]=1;
//		printf("%d ",a);
		for(int v:G[a]){
			if(!had[v]){
				c[v]=c[a]+1;
				had[v]=1;
				Q.push(v);				
			}else if(c[v]==c[a]){
				c[v]=c[a]+1;
			}
		}
	}
//	printf("\n");
}
int u,v;
int main(){
	int T;
	for(scanf("%d",&T);T;T--){
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=k;i++)had[i]=0,C[i].clear();
		for(int i=1;i<=n;i++){
			scanf("%d",&c[i]);
			G[i].clear();
			C[c[i]].push_back(i);
		}
		for(int i=1;i<=m;i++){
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			if(!had[i])bfs(i);
		}
		for(int i=1;i<=n;i++){
			if(c[i]>ans)ans=c[i];
		}
		printf("%d ",ans);
		for(int i=1;i<=n;i++){
			printf("%d ",c[i]);
		}	printf("\n");
		for(int i=1;i<=n;i++){
			if(c[i]==ans){
				dfs(i);
				break;
			}
		}	printf("\n");
	}
	return 0;
}
/*
1
7 7 4
3 4 2 1 3 4 1
6 7
3 4
3 6
3 5
6 1
2 3
2 4
*/

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 8444kb

input:

output:

result:

ok good job (2 test cases)

Test #2:

score: -100

Wrong Answer

time: 100ms

memory: 8740kb

input:

50000
5 7 5
5 2 3 1 5
4 3
3 1
5 2
5 4
5 3
2 4
4 1
6 5 5
1 1 4 5 5 2
2 3
3 5
6 1
2 4
1 5
7 5 6
4 6 3 5 6 5 3
5 4
5 6
7 2
1 2
3 6
7 7 4
3 4 2 1 3 4 1
6 7
3 4
3 6
3 5
6 1
2 3
2 4
5 6 5
3 3 4 4 1
4 5
2 3
5 2
3 1
4 2
5 1
6 6 3
2 3 2 2 1 1
2 6
3 5
2 5
6 3
4 5
4 6
7 5 2
1 2 1 1 2 2 1
5 4
5 3
7 5
1 2
3 2
7 ...

output:

5 1 5 2 3 4 
1 3 4 5 2 
5 1 4 3 5 2 2 
1 5 3 2 4 
4 1 2 1 4 3 2 3 
3 6 5 4 
4 1 1 2 3 3 4 1 
6 
4 1 3 2 4 2 
1 3 2 4 
2 1 1 1 2 2 2 
4 
2 1 2 1 1 2 2 1 
1 2 
4 1 1 1 4 2 3 1 
1 5 6 4 
3 1 2 2 2 3 
1 2 5 
3 1 3 3 2 2 3 
1 4 2 
5 1 2 4 2 5 3 
1 2 6 3 5 
5 1 1 2 1 2 3 5 
7 
6 1 3 5 2 4 3 6 
7 
4 1 1 2 ...

result:

wrong answer invalid path: there's no edge (6, 4) (test case 4)