QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491320 | #8757. 图 | yqh2025 | RE | 51ms | 7356kb | C++14 | 1.2kb | 2024-07-25 18:47:15 | 2024-07-25 18:47:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k,fa[N];
int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}
void add(int x,int y){if(find(x)!=find(y))fa[find(x)]=find(y);}
#define id(i,j) ((i-1)*n+j)
vector<int>E[N];
int vis[N],st[N],top,flag;
void dfs(int u,int goal){
st[++top]=u;vis[u]=1;
if(u==goal){
printf("%d ",top);
for(int i=1;i<=top;i++){
int x=st[i]%n;if(x==0)x=n;
printf("%d ",x);
}
puts("");
return;
}
for(int v:E[u]){
if(vis[v])continue;
dfs(v,goal);
}
top--;
}
void sol(){
scanf("%d%d",&n,&m);k=(m+n-2)/(n-1);
for(int i=1;i<=k*n;i++)fa[i]=i,E[i].clear(),vis[i]=0;
int s,t;s=t=0;
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
int ans=0;
for(int j=12;j>=0;j--){
int mid=ans+(1<<j);
if(mid>k)continue;
if(find(id(mid,x))==find(id(mid,y)))ans=mid;
}
ans++;
add(id(ans,x),id(ans,y));
if(ans==k)s=x,t=y;
E[id(ans,x)].push_back(id(ans,y));
E[id(ans,y)].push_back(id(ans,x));
}
if(!s){
puts("-1");
return;
}
printf("%d %d\n",s,t);
for(int i=1;i<=k;i++){
int x=id(i,s),y=id(i,t);
flag=0; dfs(x,y);top=0;
}
}
signed main(){
int t;cin>>t;
while(t--)sol();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 51ms
memory: 6584kb
input:
10000 2 20 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 20 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 20 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 20 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 ...
output:
2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2...
result:
ok Answer correct. (10000 test cases)
Test #2:
score: 0
Accepted
time: 36ms
memory: 6688kb
input:
10000 5 20 2 1 2 5 5 3 3 1 4 5 1 4 4 3 4 5 3 5 5 4 2 3 5 2 3 4 3 5 1 4 4 3 4 2 2 1 1 3 5 1 5 20 4 2 1 3 1 2 4 5 2 4 3 1 5 3 5 1 4 5 4 3 2 4 1 4 4 3 5 2 1 2 3 5 1 5 4 1 3 4 4 3 5 20 1 4 1 3 1 5 5 1 4 5 3 4 4 5 2 3 1 2 2 4 4 5 4 5 2 4 2 5 4 2 4 3 4 2 2 5 2 1 3 1 5 20 2 5 2 3 4 5 4 2 3 4 2 1 5 4 2 5 2 ...
output:
1 3 4 1 2 5 3 2 1 3 3 1 4 3 4 1 2 4 3 2 1 3 3 4 4 3 1 2 4 3 3 5 4 2 3 4 2 3 4 2 3 4 2 5 4 2 3 1 5 3 2 1 5 3 2 4 5 3 2 4 5 2 2 5 5 2 2 5 2 3 5 4 2 2 5 2 2 5 2 2 5 2 5 1 2 5 1 2 5 1 2 5 1 2 5 1 2 5 1 3 2 3 3 5 2 5 3 5 1 4 2 4 3 1 5 2 4 3 1 5 2 2 3 2 4 2 3 4 3 2 2 4 2 3 ...
result:
ok Answer correct. (10000 test cases)
Test #3:
score: 0
Accepted
time: 34ms
memory: 6284kb
input:
10000 10 20 9 4 8 6 2 10 2 9 7 10 4 6 9 4 2 1 4 7 1 5 7 2 4 1 5 9 7 6 8 2 9 4 5 9 9 8 7 3 2 4 10 20 3 8 8 9 8 7 9 2 3 10 9 3 8 1 9 4 8 9 4 7 7 5 5 10 1 3 3 4 3 7 3 8 3 9 1 4 3 6 2 4 10 20 7 6 8 10 3 8 2 8 4 8 4 8 4 6 4 1 1 7 4 6 5 9 5 2 4 7 10 9 6 7 10 5 2 4 4 1 3 2 4 9 10 20 2 1 9 8 7 6 2 10 9 5 4 ...
output:
2 4 3 2 9 4 3 2 7 4 2 2 4 1 4 4 1 8 9 4 3 1 3 4 2 1 4 4 1 2 4 1 3 4 7 1 2 4 1 6 2 7 6 4 3 9 5 1 2 3 6 8 2 2 6 2 3 10 5 3 2 7 4 10 4 3 9 2 10 2 3 10 1 8 3 1 7 8 6 1 10 3 2 6 8 2 1 8 6 9 4 6 4 7 9 5 6 5 7 3 9 2 6 9 1 10 2 1 10 3 1 5 10 2 1 10 10 8 3 10 6 8 4 10 9 7 8 2 10 8 ...
result:
ok Answer correct. (10000 test cases)
Test #4:
score: 0
Accepted
time: 15ms
memory: 6180kb
input:
2000 50 50 6 10 21 26 12 42 29 2 3 30 3 28 7 44 44 37 11 4 23 12 49 14 34 41 35 48 33 6 27 9 33 1 33 31 43 35 32 31 20 42 27 40 39 29 34 38 21 15 31 17 3 33 17 18 15 44 50 22 20 25 28 44 23 32 3 23 25 30 50 20 17 2 21 41 46 35 26 7 34 45 34 19 21 10 44 4 28 22 36 21 4 49 44 39 4 36 2 15 21 38 50 50 ...
output:
21 38 4 21 41 34 38 2 21 38 7 10 6 7 36 24 9 37 10 2 7 10 23 26 13 23 21 24 14 36 10 1 8 40 28 3 43 26 2 23 26 39 16 2 39 16 2 39 16 37 11 8 37 12 43 50 17 19 35 11 2 37 11 38 46 11 38 45 19 30 9 22 41 12 31 3 46 2 38 46 3 11 10 3 6 2 13 7 31 15 22 32 11 2 3 11 46 17 9 46 42 36 26 27 2...
result:
ok Answer correct. (2000 test cases)
Test #5:
score: 0
Accepted
time: 36ms
memory: 6564kb
input:
200 50 1000 6 33 31 2 17 37 27 22 36 1 35 12 31 3 8 36 22 15 40 45 13 23 23 24 50 46 41 48 49 35 15 30 14 6 7 24 38 27 43 19 30 16 16 31 49 21 47 44 33 9 27 32 48 23 24 33 25 12 23 50 6 27 20 21 48 11 42 23 8 36 3 34 8 14 17 30 27 1 14 40 37 5 23 24 6 24 5 35 38 43 31 48 25 33 4 13 6 37 22 24 31 32 ...
output:
31 38 7 31 16 30 15 22 27 38 17 31 32 25 33 34 23 24 6 27 1 47 36 8 2 4 10 38 10 31 47 43 34 27 30 50 29 17 38 9 31 30 13 7 24 29 17 48 38 10 31 5 32 40 29 9 49 37 2 38 6 31 1 25 6 37 38 3 31 43 38 8 31 35 33 22 6 43 8 38 8 31 41 10 47 45 14 8 38 8 31 20 22 41 11 14 3 38 5 31 23 29 15 38 ...
result:
ok Answer correct. (200 test cases)
Test #6:
score: 0
Accepted
time: 37ms
memory: 7356kb
input:
20 100 10000 77 84 14 62 84 5 4 67 99 44 54 18 39 53 58 88 32 3 61 19 76 14 28 72 92 34 20 1 14 66 98 25 53 99 55 40 13 70 42 62 32 41 93 14 74 66 92 62 42 12 94 35 26 65 82 85 100 34 79 47 87 59 4 92 46 4 77 63 17 62 32 23 46 76 61 26 89 41 10 18 17 64 55 61 89 42 8 71 75 89 2 81 9 63 42 32 23 34 7...
output:
39 61 11 39 53 99 20 89 42 62 92 4 26 61 3 39 69 61 14 39 52 25 66 96 91 72 46 98 31 22 19 73 61 2 39 61 10 39 69 17 47 100 88 44 49 11 61 23 39 9 79 88 20 80 12 63 44 99 40 4 73 100 14 76 27 29 43 28 15 93 61 10 39 31 65 86 15 10 13 48 12 61 15 39 75 93 47 69 87 16 88 99 57 49 1 46 43 61 11...
result:
ok Answer correct. (20 test cases)
Test #7:
score: 0
Accepted
time: 32ms
memory: 6472kb
input:
100 1000 1999 527 98 626 570 505 814 510 660 334 873 893 329 51 818 256 113 165 543 515 780 905 200 560 363 385 813 82 324 661 719 3 624 175 120 22 480 662 730 701 676 124 107 820 707 288 412 596 842 285 574 209 109 897 789 37 371 399 502 715 361 877 504 68 73 919 671 685 732 866 390 975 122 994 263...
output:
183 97 14 183 906 447 101 368 216 113 256 645 629 510 660 786 97 19 183 942 643 548 798 886 89 569 820 999 313 278 968 756 703 946 253 732 97 2 183 97 906 933 8 906 48 943 924 937 197 39 933 28 906 536 924 307 206 369 443 827 692 304 774 614 529 778 163 87 339 691 830 268 491 960 464 559 853 648...
result:
ok Answer correct. (100 test cases)
Test #8:
score: 0
Accepted
time: 11ms
memory: 6088kb
input:
1000 100 100 8 93 14 86 43 53 73 87 9 5 30 87 23 88 9 18 89 75 49 53 39 91 58 22 86 27 75 1 57 90 20 40 71 55 58 77 63 46 97 95 6 71 19 92 54 24 50 96 30 50 11 79 70 20 79 24 88 33 8 86 18 60 51 58 66 39 93 31 1 47 41 65 45 12 3 93 62 33 38 49 29 91 3 29 15 51 37 56 54 6 85 95 2 81 36 28 10 98 57 26...
output:
78 56 24 78 23 88 33 62 9 70 20 40 43 53 76 27 86 8 93 3 29 91 87 30 50 96 56 2 78 56 18 45 11 18 85 59 69 1 23 75 47 13 93 45 2 18 45 9 92 9 9 69 24 30 15 34 85 57 92 2 9 92 7 60 23 7 99 61 63 43 84 78 26 13 98 55 72 15 42 76 21 75 23 88 86 67 87 60 2 7 60 13 57 16 13 70 19 71 4 74 86 93 46...
result:
ok Answer correct. (1000 test cases)
Test #9:
score: 0
Accepted
time: 31ms
memory: 6340kb
input:
500 200 399 181 137 41 68 61 54 32 10 41 136 85 112 127 111 51 107 143 189 21 69 149 109 107 120 21 158 175 53 31 48 80 170 46 108 163 85 110 142 2 30 117 128 109 114 142 178 76 43 118 63 36 149 45 74 165 123 43 72 87 185 70 173 132 79 130 163 187 10 189 114 70 22 12 184 200 175 65 169 23 27 1 14 19...
output:
98 125 15 98 24 75 59 104 110 142 188 170 80 79 200 175 78 125 20 98 90 189 53 150 190 132 45 186 61 178 116 14 157 160 20 17 198 13 125 2 98 125 83 102 16 83 112 13 28 10 128 64 33 57 124 31 4 120 167 107 102 12 83 88 176 50 89 78 161 127 132 87 172 102 2 83 102 28 7 10 28 58 45 17 140 75 170...
result:
ok Answer correct. (500 test cases)
Test #10:
score: 0
Accepted
time: 27ms
memory: 6976kb
input:
2197 10 91 7 3 7 9 9 2 1 10 7 1 6 8 4 8 2 10 7 6 5 3 4 10 9 3 1 4 2 9 5 4 5 6 3 7 6 1 1 9 2 6 3 4 6 9 8 7 6 7 7 4 8 7 9 3 10 7 10 6 2 5 2 7 8 10 10 1 7 4 10 4 9 2 7 6 3 10 6 4 1 8 8 9 6 7 10 9 3 2 2 5 10 5 4 7 5 3 9 4 1 5 1 4 8 4 4 10 7 3 6 7 4 2 3 4 9 2 1 10 6 1 8 3 2 9 9 10 9 5 3 4 5 8 9 3 7 1 6 1...
output:
2 4 6 2 9 7 6 8 4 3 2 10 4 4 2 6 7 4 3 2 7 4 3 2 9 4 5 2 3 5 1 4 2 2 4 2 2 4 5 2 10 5 6 4 2 2 4 2 2 4 4 7 3 4 2 7 3 4 2 7 3 4 2 7 2 4 7 4 4 8 2 7 3 4 9 7 4 4 5 8 7 4 4 8 1 7 3 4 2 7 2 4 7 2 4 7 2 5 3 2 8 5 6 2 6 7 1 9 5 3 2 6 5 3 2 6 5 3 2 1 5 5 2 1 7 8 5 5 2 4 9 3 5 5 2...
result:
ok Answer correct. (2197 test cases)
Test #11:
score: 0
Accepted
time: 39ms
memory: 6164kb
input:
1980 5 101 3 5 4 2 5 1 1 4 2 5 1 3 2 5 3 2 4 2 3 1 1 2 5 3 3 4 3 1 1 3 5 3 1 4 2 4 2 3 4 2 4 5 4 5 1 2 3 1 3 4 1 2 3 5 4 1 2 4 3 5 4 3 4 1 2 1 2 1 5 4 5 3 3 5 2 5 4 1 5 3 2 3 3 4 3 4 5 2 3 2 4 3 2 3 4 3 1 5 2 1 1 3 1 4 1 4 2 5 2 1 1 3 3 5 5 3 1 5 3 4 4 2 3 5 4 2 2 4 4 1 3 5 3 5 5 4 1 4 5 3 5 1 5 3 1...
output:
1 3 3 1 5 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 4 1 4 5 3 3 1 4 3 4 1 2 5 3 3 1 2 3 3 1 5 3 3 1 2 3 2 1 3 3 1 4 3 2 1 3 3 1 4 3 4 1 4 5 3 3 1 5 3 3 1 4 3 3 1 5 3 2 1 3 4 1 2 5 3 2 1 3 2 1 3 2 1 3 2 1 3 2 4 4 2 1 3 4 3 2 3 4 3 2 3 4 4 2 5 1 4 2 2 4 2 2 4 4 2 3 1 4 3 2 5 4 ...
result:
ok Answer correct. (1980 test cases)
Test #12:
score: -100
Runtime Error
input:
1 100000 200000 34863 14128 21925 31963 32836 60679 64214 73508 66150 45252 9601 33518 33904 58681 94179 37263 91962 58845 44150 57595 75389 55087 95549 80645 35339 82663 93639 89411 91288 79966 6158 91046 34153 16675 38098 20451 49822 20670 34821 40807 67167 98424 75186 55129 47388 80048 47576 3327...