QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#781489	#9743. 重心树	Zpair	AC ✓	48ms	14840kb	C++20	667b	2024-11-25 16:15:19	2024-11-25 16:15:22

Judging History

This is the latest submission verdict.

[2024-11-25 16:15:22]
Judged

Verdict: AC
Time: 48ms
Memory: 14840kb

Show

[2024-11-25 16:15:19]
Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
vector<int> e[N];
int fa[N];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		e[i].clear(),fa[i]=i;
	for(int i=1;i<=n;++i){
		int x,y;
		scanf("%d",&x);
		while(x--){
			scanf("%d",&y);
			e[i].push_back(y);
		}
	}
	vector<pair<int, int> > ans;
	for(int i=n;i>=1;--i){
		for(int x:e[i]){
			x=find(x);
			ans.push_back({find(x),find(i)});
			fa[x]=find(i);
		}
	}
	for(auto [x,y]:ans)
		printf("%d %d\n",x,y);
}
int main(){
	int T;cin>>T;
	while(T--)solve();
}
/*
1
5
1 3
2 5 4
1 5
0
0
*/

Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3808kb

input:

output:

result:

ok Accepted (2 test cases)

Test #2:

score: 0

Accepted

time: 18ms

memory: 4060kb

input:

output:

result:

ok Accepted (40000 test cases)

Test #3:

score: 0

Accepted

time: 6ms

memory: 4088kb

input:

output:

result:

ok Accepted (10000 test cases)

Test #4:

score: 0

Accepted

time: 11ms

memory: 3860kb

input:

output:

result:

ok Accepted (10000 test cases)

Test #5:

score: 0

Accepted

time: 0ms

memory: 4116kb

input:

16
392
4 2 3 165 13
0
2 4 12
0
4 177 7 9 23
2 187 16
0
1 13
0
1 13
2 208 27
0
2 14 22
0
1 23
2 19 20
1 208
3 21 25 27
0
0
0
0
0
2 208 29
0
2 32 31
3 44 40 38
1 208
0
1 44
0
3 35 49 52
1 42
2 36 208
0
0
1 44
1 42
1 49
1 60
2 79 213
0
3 46 79 57
2 47 48
1 60
0
0
0
0
1 213
1 79
1 64
1 57
2 79 63
2 62 2...

output:

result:

ok Accepted (16 test cases)

Test #6:

score: 0

Accepted

time: 1ms

memory: 3848kb

input:

4
502
3 3 253 10
3 7 8 13
2 15 18
1 15
2 6 253
0
1 24
0
1 18
0
2 23 20
2 258 21
1 33
2 24 17
1 24
1 20
0
2 25 26
3 27 42 264
0
2 22 31
0
1 33
2 30 34
0
0
0
1 42
2 265 37
0
0
1 45
0
0
2 269 52
2 269 44
0
1 45
1 56
2 51 58
3 43 47 269
2 54 50
0
0
1 60
1 51
0
1 58
2 53 269
0
0
2 61 63
0
1 60
2 278 67
1...

output:

result:

ok Accepted (4 test cases)

Test #7:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

1
422
2 9 195
1 9
4 5 195 11 8
1 13
1 13
3 212 12 25
2 16 14
0
0
2 18 212
2 19 31
0
0
0
2 22 29
1 27
1 22
0
1 27
3 221 26 30
1 31
0
1 222
2 33 37
2 33 35
0
0
1 222
1 34
0
0
1 40
2 48 49
1 48
0
2 38 229
2 42 41
0
1 56
1 42
0
0
1 50
3 86 47 238
2 86 51
1 86
0
1 56
1 50
0
0
2 238 58
2 94 57
1 238
1 96
...

output:

result:

ok Accepted (1 test case)

Test #8:

score: 0

Accepted

time: 16ms

memory: 4024kb

input:

100
509
3 21 3 252
1 21
0
2 23 18
3 252 8 25
2 252 14
2 11 26
0
1 18
1 252
0
1 252
1 26
0
1 34
2 42 22
1 28
1 28
2 24 252
1 51
2 72 39
2 30 31
1 72
0
1 34
1 75
1 39
0
1 252
0
0
1 75
1 252
0
4 37 40 266 46
2 38 39
0
0
3 41 44 48
0
0
1 75
1 266
0
1 53
2 59 62
3 49 266 56
0
0
1 266
1 75
1 266
1 60
1 56...

output:

result:

ok Accepted (100 test cases)

Test #9:

score: 0

Accepted

time: 29ms

memory: 6352kb

input:

5
4174
3 9 15 2088
3 3 18 7
0
2 23 12
1 15
2 19 2088
0
1 19
1 23
2 11 2088
3 16 17 21
0
1 20
2 2088 38
0
0
0
2 28 27
1 20
0
0
2 2088 39
1 34
2 30 47
1 30
2 29 2088
0
1 34
0
0
1 39
1 47
1 2088
0
1 39
1 51
2 2088 44
2 42 51
2 46 49
2 55 2088
1 42
0
1 44
0
1 55
0
2 48 52
0
0
2 2088 58
2 59 53
1 63
0
2 ...

output:

result:

ok Accepted (5 test cases)

Test #10:

score: 0

Accepted

time: 26ms

memory: 6516kb

input:

4
32538
4 21 46 18 16255
2 14 22
1 46
1 17
1 18
2 8 50
2 16 11
1 16
1 16255
1 50
0
2 20 22
1 18
1 17
2 16272 33
0
0
2 23 27
1 50
0
2 32 28
2 30 36
0
1 16272
3 26 38 37
0
0
0
1 50
0
1 16272
1 36
2 42 53
1 39
1 50
0
1 39
3 51 44 48
0
1 50
1 16272
1 55
1 62
0
2 16299 78
1 59
1 16299
0
1 59
2 56 67
1 55...

output:

32533 32531
32536 32530
32538 32530
32531 32529
32537 32529
32528 32527
32530 32527
32534 32526
32532 32525
32535 32525
32529 32521
32524 32520
32519 32518
32523 32517
32526 32517
32527 32517
32521 32516
32522 32516
32525 32516
32516 32515
32518 32515
32520 32513
32512 32511
32515 32511
32517 32511
...

result:

ok Accepted (4 test cases)

Test #11:

score: 0

Accepted

time: 19ms

memory: 7272kb

input:

3
54304
3 7 27151 13
1 7
3 11 8 27158
2 6 11
1 22
2 9 12
0
0
0
1 27158
3 14 17 31
0
2 25 22
2 15 23
0
1 25
0
1 31
1 27158
1 26
2 36 27158
3 27 28 34
0
1 40
1 26
0
0
0
1 36
2 27158 48
1 40
1 34
2 41 27158
0
1 41
0
5 27175 42 45 46 73
1 48
1 27175
0
0
0
2 52 58
1 27175
0
0
2 50 73
2 49 57
0
0
3 54 56 ...

output:

54303 54301
54304 54301
54296 54295
54300 54294
54298 54293
54301 54293
54297 54292
54302 54292
54293 54291
54299 54290
54294 54289
54295 54289
54290 54288
54292 54288
54289 54286
54288 54284
54291 54284
54284 54282
54286 54282
54283 54281
54287 54281
54280 54279
54285 54279
54282 54278
54281 54277
...

result:

ok Accepted (3 test cases)

Test #12:

score: 0

Accepted

time: 15ms

memory: 7592kb

input:

2
64362
6 2 13 32175 17 6 18
0
3 15 11 23
2 32175 14
1 17
0
1 15
1 11
1 18
2 32175 20
0
2 22 21
1 28
0
0
1 32175
2 22 24
0
1 32175
0
0
2 27 32
2 25 33
0
0
2 31 32175
0
1 33
2 36 40
1 36
1 36
0
0
3 32175 48 42
1 32175
2 37 46
0
1 40
2 56 45
0
1 56
0
3 32182 80 60
3 32182 52 53
0
0
1 80
1 57
2 32192 7...

output:

64361 64355
64355 64354
64362 64354
64357 64351
64360 64351
64358 64350
64359 64350
64356 64348
64352 64346
64353 64346
64346 64345
64354 64345
64344 64342
64350 64342
64351 64342
64343 64341
64348 64341
64341 64339
64349 64339
64339 64338
64340 64338
64347 64338
64345 64337
64336 64334
64342 64333
...

result:

ok Accepted (2 test cases)

Test #13:

score: 0

Accepted

time: 48ms

memory: 14652kb

input:

1
194798
3 2 3 97357
0
0
3 6 8 97357
1 6
0
2 16 32
1 24
3 97357 14 19
2 97357 13
2 97357 20
1 32
0
0
2 97357 29
2 28 26
1 97357
2 97357 27
0
0
1 29
1 37
1 97357
1 28
2 35 97357
0
0
0
0
1 35
4 33 34 97357 45
1 37
0
0
0
2 38 97357
0
0
3 97357 48 67
1 45
1 50
1 97357
2 97361 47
3 106 97382 59
1 50
1 48...

output:

194795 194794
194798 194793
194793 194792
194794 194792
194797 194792
194790 194789
194796 194787
194792 194786
194786 194785
194788 194784
194791 194784
194787 194781
194789 194781
194783 194779
194784 194778
194780 194776
194781 194776
194785 194776
194782 194773
194775 194772
194777 194771
194779...

result:

ok Accepted (1 test case)

Test #14:

score: 0

Accepted

time: 15ms

memory: 4100kb

input:

output:

result:

ok Accepted (10000 test cases)

Test #15:

score: 0

Accepted

time: 17ms

memory: 3768kb

input:

10000
14
2 2 10
4 6 4 5 12
1 6
2 7 9
2 11 13
0
0
1 14
0
1 14
0
0
0
0
11
4 4 5 6 11
2 7 10
1 5
2 8 9
0
0
1 8
0
0
0
0
9
4 3 4 6 7
1 8
2 5 9
0
0
0
0
1 9
0
16
2 8 7
2 12 8
1 12
1 8
1 7
1 13
0
4 9 10 15 16
0
0
1 15
1 13
0
1 16
0
0
10
3 4 3 7
2 10 5
0
1 10
0
1 7
2 8 9
0
0
0
5
3 5 3 4
1 5
0
0
0
7
2 3 5
2 3...

output:

result:

ok Accepted (10000 test cases)

Test #16:

score: 0

Accepted

time: 19ms

memory: 3812kb

input:

10000
17
2 2 12
4 14 6 11 10
2 7 12
1 14
1 6
0
0
2 15 13
1 12
0
1 15
2 16 17
0
0
0
0
0
9
3 5 4 9
1 5
1 4
0
2 7 8
1 9
0
0
0
5
2 3 5
1 4
1 4
0
0
18
3 4 3 10
2 9 16
0
2 14 12
3 8 15 11
1 18
1 14
0
1 13
1 17
0
1 13
0
0
1 17
1 18
0
0
2
1 2
0
14
3 3 13 7
2 6 11
1 10
1 13
2 8 14
1 10
1 12
1 12
1 14
0
0
0
0...

output:

result:

ok Accepted (10000 test cases)

Test #17:

score: 0

Accepted

time: 21ms

memory: 4056kb

input:

output:

result:

ok Accepted (10000 test cases)

Test #18:

score: 0

Accepted

time: 18ms

memory: 3792kb

input:

output:

result:

ok Accepted (100000 test cases)

Test #19:

score: 0

Accepted

time: 47ms

memory: 14840kb

input:

output:

199998 199997
199988 199987
199985 199984
199983 199982
199980 199979
199976 199975
199972 199971
199968 199967
199965 199964
199960 199959
199959 199958
199958 199957
199947 199946
199940 199939
199938 199937
199933 199932
199931 199930
199924 199923
199915 199914
199914 199913
199912 199911
199908...

result:

ok Accepted (1 test case)

Test #20:

score: 0

Accepted

time: 39ms

memory: 9016kb

input:

1
200000
5703 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 1374 1375 1440 1486 1487 1488 1489 1845 1846 1847 1848 1849 1850 1851 1860 1861 1862 1863 1864 1865 1866 1867 1868 1888 1889 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3446 ...

output:

199908 199907
199909 199907
199910 199907
199911 199907
199912 199907
199913 199907
199914 199907
199915 199907
199916 199907
199917 199907
199918 199907
199919 199907
199920 199907
199921 199907
199922 199907
199923 199907
199924 199907
199925 199907
199926 199907
199927 199907
199928 199907
199929...

result:

ok Accepted (1 test case)

Test #21:

score: 0

Accepted

time: 46ms

memory: 14168kb

input:

1
200000
11 39 63012 63019 63148 63219 63220 63262 63263 130152 198563 199731
9 3 4 39 60342 60876 60977 62603 62911 62944
0
5 5 7 23 25 36
0
3 8 19 22
4 8 15 16 18
4 9 10 12 14
0
0
1 13
1 13
0
0
0
0
1 18
0
2 20 21
0
0
0
0
2 27 31
2 26 29
0
2 28 30
0
1 30
0
3 32 33 35
0
0
1 35
0
2 37 38
0
0
15 41 42...

output:

200000 199999
199998 199997
199999 199997
199995 199994
199996 199994
199992 199991
199989 199988
199986 199985
199981 199980
199982 199980
199980 199979
199979 199978
199983 199978
199978 199977
199984 199977
199985 199977
199987 199977
199988 199977
199990 199977
199975 199974
199976 199974
199977...

result:

ok Accepted (1 test case)

Test #22:

score: 0

Accepted

time: 39ms

memory: 10684kb

input:

output:

99993 99992
99987 99986
99986 99985
99983 99982
99982 99981
99980 99979
99977 99976
99969 99968
99963 99962
99959 99958
99955 99954
99954 99953
99953 99952
99950 99949
99947 99946
99942 99941
99935 99934
99934 99933
99936 99933
99933 99932
99932 99931
99928 99927
99924 99923
99923 99922
99922 99921
...

result:

ok Accepted (2 test cases)

Test #23:

score: 0

Accepted

time: 25ms

memory: 8608kb

input:

2
100000
2810 2 3 4 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 951 952 953 1008 1009 1010 1019 1020 1021 1046 1047 1048 1049 1050 1581 1582 1583 1584 1585 1586 1587 1588 1589 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1680 1693 1694 1711 1712 1713 1732 1733 1951 1952 2040 20...

output:

99816 99815
99817 99815
99818 99815
99819 99815
99820 99815
99821 99815
99822 99815
99823 99815
99824 99815
99825 99815
99826 99815
99827 99815
99828 99815
99829 99815
99830 99815
99831 99815
99832 99815
99833 99815
99834 99815
99835 99815
99836 99815
99837 99815
99838 99815
99839 99815
99840 99815
...

result:

ok Accepted (2 test cases)

Extra Test:

score: 0

Extra Test Passed