QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491618 | #8757. 图 | bai_hong | RE | 46ms | 11064kb | C++14 | 1.5kb | 2024-07-25 20:31:28 | 2024-07-25 20:31:30 |
Judging History
answer
//Shirosaki Hana kawaii
#include<bits/stdc++.h>
const int QWQ=2e5+5;
using namespace std;
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar())
if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
int T,n,m,K,fa[QWQ],pre[QWQ],vis[QWQ];
vector<int> E[QWQ],vec;
int get(int k){
if (fa[k]==k) return k;
return fa[k]=get(fa[k]);
}
signed main(){
for (T=read();T--;){
n=read(),m=read(),K=ceil(m*1.0/(n-1));
for (int t=1;t<=K;t++)
for (int i=1;i<=n;i++) fa[(t-1)*n+i]=(t-1)*n+i;
for (int i=1;i<=m;i++){
int u=read(),v=read();
for (int t=1;t<=K;t++){
int A=get((t-1)*n+u);
int B=get((t-1)*n+v);
if (A!=B){
E[(t-1)*n+u].push_back((t-1)*n+v);
E[(t-1)*n+v].push_back((t-1)*n+u);
fa[B]=A; break;
}
}
}
int u=0,v=0;
for (int i=1;i<=n;i++)
if (fa[(K-1)*n+i]!=(K-1)*n+i)
u=fa[(K-1)*n+i]-(K-1)*n,v=i;
printf("%d %d\n",u,v);
for (int d=1;d<=K;d++){
int s=(d-1)*n+u,t=(d-1)*n+v;
queue<int> q; q.push(s),vis[s]=1;
while (!q.empty()){
int now=q.front(); q.pop();
for (int to:E[now]) if (!vis[to])
pre[to]=now,q.push(to),vis[to]=1;
}
vec.clear(),vec.push_back(v);
for (int i=pre[t];i;i=pre[i])
vec.push_back(i-(d-1)*n);
reverse(vec.begin(),vec.end());
printf("%d ",(int)vec.size());
for (int x:vec) printf("%d ",x); puts("");
}
for (int i=1;i<=K*n;i++)
E[i].clear(),pre[i]=vis[i]=0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 46ms
memory: 9400kb
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: 24ms
memory: 8884kb
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 5 3 1 2 5 3 1 4 5 4 1 4 3 5 4 1 2 4 5 3 1 3 5 1 5 4 1 2 4 5 3 1 3 5 2 1 5 3 1 2 5 2 1 5 2 5 4 2 3 1 5 3 2 1 5 3 2 4 5 3 2 4 5 2 2 5 1 4 4 1 2 5 4 3 1 2 4 4 1 3 5 4 3 1 3 4 3 1 2 4 4 5 2 4 5 2 4 5 3 4 1 5 3 4 1 5 3 4 3 5 2 5 2 2 5 4 2 4 1 5 2 2 5 2 2 5 2 2 5 4 5 4 4 3 ...
result:
ok Answer correct. (10000 test cases)
Test #3:
score: 0
Accepted
time: 14ms
memory: 9472kb
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:
5 9 4 5 1 2 9 2 5 9 2 5 9 3 9 3 3 8 9 2 3 9 2 3 9 6 7 2 6 7 3 6 4 7 2 6 7 4 10 7 4 3 9 5 1 2 10 5 4 2 9 5 10 2 4 10 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 3 9 2 3 9 2 3 9 3 3 4 9 1 10 2 1 10 3 1 5 10 2 1 10 7 8 3 7 5 8 2 7 8 2 7 8 4 10 3 4 6 1...
result:
ok Answer correct. (10000 test cases)
Test #4:
score: 0
Accepted
time: 9ms
memory: 9376kb
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:
44 39 9 44 28 3 33 31 17 2 29 39 2 44 39 36 49 7 36 24 9 37 10 4 49 2 36 49 23 33 6 23 21 24 14 6 33 2 23 33 42 50 5 42 26 21 12 50 2 42 50 43 50 2 43 50 2 43 50 29 48 12 29 24 3 31 12 42 23 10 35 6 16 48 3 29 43 48 15 47 6 15 31 7 13 2 47 2 15 47 32 47 2 32 47 2 32 47 33 44 4 33 9 3...
result:
ok Answer correct. (2000 test cases)
Test #5:
score: 0
Accepted
time: 21ms
memory: 11064kb
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 50 11 31 16 30 15 22 27 6 33 24 23 50 7 31 32 25 33 34 23 50 7 31 47 43 34 27 30 50 6 31 30 13 7 24 50 11 31 5 32 40 29 9 49 37 2 38 50 14 31 1 25 6 37 38 21 28 15 29 36 16 12 50 9 31 43 44 2 17 6 46 47 50 12 31 35 33 22 6 26 39 28 11 40 48 50 9 31 41 10 47 45 4 20 12 50 5 31 20 22 9 50 ...
result:
ok Answer correct. (200 test cases)
Test #6:
score: 0
Accepted
time: 41ms
memory: 10396kb
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 86 14 39 53 99 20 89 42 62 92 4 26 61 55 40 86 17 39 69 22 11 68 12 66 60 87 41 64 5 24 38 47 27 86 8 39 52 64 12 59 95 23 86 12 39 68 71 72 98 36 41 57 29 97 11 86 11 39 69 17 76 20 42 26 78 3 45 86 19 39 9 79 88 20 80 12 63 44 99 40 4 73 100 14 76 77 37 86 4 39 31 65 86 22 39 75 93 47 69...
result:
ok Answer correct. (20 test cases)
Test #7:
score: 0
Accepted
time: 13ms
memory: 9808kb
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:
792 995 35 792 326 646 195 811 149 312 288 43 680 999 471 902 173 322 848 597 974 239 340 169 883 485 495 375 899 172 53 518 786 97 393 686 700 995 47 792 37 190 548 798 886 89 569 820 999 313 278 968 756 703 312 546 972 315 90 876 598 716 57 429 902 26 757 552 614 216 450 724 571 515 910 866 185 4...
result:
ok Answer correct. (100 test cases)
Test #8:
score: 0
Accepted
time: 8ms
memory: 9740kb
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: 13ms
memory: 10276kb
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:
102 200 11 102 134 152 121 168 68 41 156 80 79 200 19 102 70 87 8 174 97 12 157 160 20 17 198 13 176 48 101 42 29 200 2 102 200 39 179 33 39 156 17 92 5 150 174 11 112 13 28 10 128 64 33 57 124 31 4 120 167 191 173 121 98 185 131 63 129 80 136 196 179 12 39 76 23 66 77 142 125 147 133 193 71 179...
result:
ok Answer correct. (500 test cases)
Test #10:
score: 0
Accepted
time: 19ms
memory: 9744kb
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:
3 8 4 3 7 6 8 3 3 7 8 4 3 4 7 8 5 3 9 6 10 8 4 3 10 9 8 5 3 5 1 4 8 2 3 8 7 3 9 10 6 1 7 8 4 3 6 5 8 3 3 5 8 4 3 2 4 8 8 9 3 8 3 9 6 8 4 2 7 5 9 5 8 5 3 1 9 4 8 6 7 9 6 8 2 7 1 5 9 3 8 7 9 4 8 5 3 9 3 8 1 9 2 8 9 2 8 9 2 8 9 7 10 3 7 4 10 3 7 8 10 6 7 4 6 2 3 10 6 7 4 9 6 5 ...
result:
ok Answer correct. (2197 test cases)
Test #11:
score: 0
Accepted
time: 34ms
memory: 9548kb
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 3 4 2 3 4 2 3 4 2 3 4 3 3 1 4 5 3 1 5 2 4 4 3 5 2 4 3 3 1 4 4 3 1 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...