QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #83934 | #5655. Train Splitting | lc174 | WA | 21ms | 3752kb | C++14 | 1.1kb | 2023-03-04 14:32:06 | 2023-03-04 14:32:07 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
int n,m,t,x[2500],y[2500],ans[2500];
bool vis[2500];
vector<int> point[51];
void dfs(int u,int s){
vis[u]=true;
for(int v:point[u])if(v!=s&&!vis[v])dfs(v,s);
}
int main(){
scanf("%d",&t);
for(int i=1;i<=t;++i){
scanf("%d%d",&n,&m);
for(int j=1;j<=n;++j)point[j].clear();
for(int j=1;j<=m;++j){
scanf("%d%d",x+j,y+j);
point[x[j]].push_back(y[j]);
point[y[j]].push_back(x[j]);
}
for(int j=1;j<=n;++j){
memset(vis,0,sizeof(vis));
dfs(1,j);
bool flag=true;
for(int k=1;k<=n;++k)if(!vis[k]&&k!=j){
flag=false;
break;
}
if(flag){
if(point[j].size()==n-1){
puts("3");
int u=(j==1?2:1);
for(int k=1;k<=m;++k)if(x[k]==j)if(y[k]==u)printf("3 ");else printf("2 ");else if(y[k]==j)if(x[k]==u)printf("3 ");else printf("2 ");else printf("1 ");
}
else{
puts("2");
for(int k=1;k<=m;++k)printf("%d ",x[k]==j||y[k]==j?2:1);
}
puts("");
break;
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3480kb
input:
2 5 9 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 3 3 1 2 3 1 2 3
output:
3 3 2 2 2 1 1 1 1 1 3 3 2 1
result:
ok OK (2 test cases)
Test #2:
score: 0
Accepted
time: 21ms
memory: 3752kb
input:
100 50 1225 15 33 19 23 14 8 23 26 5 46 22 8 22 13 16 10 20 12 32 16 2 5 36 43 20 33 35 8 4 11 15 43 4 26 33 1 25 36 49 6 11 2 35 11 39 20 24 7 41 2 10 9 40 49 27 17 26 11 49 39 46 27 24 44 26 34 6 27 25 22 9 46 29 43 50 43 2 37 37 10 28 5 14 5 23 28 37 40 10 45 9 26 23 29 35 47 32 21 16 11 9 50 50 ...
output:
3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok OK (100 test cases)
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3632kb
input:
554 8 7 1 3 5 3 6 2 3 6 4 6 7 5 8 7 8 7 7 3 3 4 7 1 2 8 1 5 7 6 5 2 10 9 10 1 8 10 4 10 3 10 10 5 6 10 2 10 7 10 10 9 8 7 2 5 1 2 3 6 6 7 8 2 2 7 5 4 10 9 9 6 3 4 5 1 2 5 7 10 3 10 2 6 8 9 1 7 9 8 6 7 1 7 7 5 2 7 3 7 7 9 4 7 7 8 9 8 7 5 4 1 8 6 5 2 4 9 6 1 7 8 2 3 8 7 8 3 7 6 7 1 1 8 4 5 3 2 5 6 8 7...
output:
2 2 1 1 1 1 1 1 2 1 1 2 1 2 1 1 2 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 2 1 1 2 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 2 1 2 1 1 1 2 1 1 2 1 1 2 2 1 1 1 2 2 1 1 1 2 1 1 2 1 1 2 2 1 1 1 1 2 1 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 2 2 1 1 1 2 2 1 1 1 1 2 1 1 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1...
result:
wrong answer colors 1 and 2 are not connected (test case 17)