QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491618#8757. 图bai_hongRE 46ms11064kbC++141.5kb2024-07-25 20:31:282024-07-25 20:31:30

Judging History

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

  • [2024-07-25 20:31:30]
  • 评测
  • 测评结果:RE
  • 用时:46ms
  • 内存:11064kb
  • [2024-07-25 20:31:28]
  • 提交

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...

output:


result: