QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602457#6294. 树3un_larryfunc100 ✓443ms65056kbC++204.9kb2024-10-01 01:26:302024-10-01 01:26:32

详细


Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 59ms
memory: 36508kb

input:

500 499 100000
136 1
182 1
117 1
450 1
295 450
243 1
149 243
490 1
122 1
325 122
467 1
367 243
28 467
370 1
50 450
73 370
125 117
145 1
326 1
67 1
35 136
350 73
32 326
404 367
448 125
60 243
306 117
68 325
419 306
392 145
463 350
55 1
314 404
37 73
356 370
227 392
291 117
18 60
348 145
87 356
143 28...

output:

19
49
11
22
32
26
25
28
22
32
40
14
33
33
11
34
19
41
36
17
13
16
32
38
9
6
25
32
18
5
39
29
16
16
35
19
16
19
26
31
10
17
45
10
21
15
39
40
12
36
42
40
31
28
28
24
31
17
22
33
22
36
10
21
19
22
34
31
30
34
32
27
37
45
20
25
36
31
27
31
31
24
16
31
9
28
27
19
26
22
22
12
20
18
19
33
27
25
45
43
15
5...

result:

ok 100000 lines

Test #2:

score: 5
Accepted
time: 61ms
memory: 40408kb

input:

500 499 100000
398 1
360 1
356 1
230 1
311 398
145 1
427 230
37 1
456 145
130 1
494 1
363 37
272 1
146 130
306 356
348 1
22 146
313 1
492 494
174 37
440 145
73 174
64 313
472 37
464 1
86 146
241 1
326 174
403 398
79 145
449 306
298 145
471 363
171 348
350 1
257 363
52 174
11 326
408 348
81 130
195 2...

output:

11
22
22
23
28
21
41
35
38
21
30
24
21
16
40
51
24
9
41
8
18
38
22
35
41
21
23
25
22
30
13
23
52
32
30
19
44
21
18
27
36
22
17
33
23
39
35
16
22
45
17
40
37
26
45
22
23
31
21
33
45
11
21
14
11
48
12
35
46
39
27
40
26
28
35
11
21
17
30
50
35
15
41
13
25
24
20
20
29
15
30
33
8
40
37
16
17
31
28
20
20
...

result:

ok 100000 lines

Test #3:

score: 5
Accepted
time: 62ms
memory: 36412kb

input:

500 499 100000
148 1
349 148
458 1
265 1
346 148
473 1
300 1
25 1
230 1
17 1
33 346
108 148
414 300
328 1
61 17
335 25
307 473
185 473
336 185
75 265
10 230
264 25
70 1
221 265
112 33
171 10
135 230
355 335
66 17
126 1
139 1
232 126
149 230
440 355
24 346
365 1
140 185
469 264
143 185
496 221
403 35...

output:

6
31
28
18
27
36
9
28
28
34
29
39
34
22
35
22
46
21
37
26
36
42
22
13
41
37
45
18
16
13
26
17
20
24
30
40
35
19
42
36
32
15
36
31
35
32
31
29
47
47
18
18
30
32
22
34
28
38
35
29
11
20
48
40
43
17
17
9
13
31
35
22
17
27
48
11
24
30
33
34
29
30
6
19
21
42
45
31
22
40
35
35
40
10
38
45
25
34
18
37
18
1...

result:

ok 100000 lines

Test #4:

score: 5
Accepted
time: 59ms
memory: 40468kb

input:

500 499 100000
197 1
324 197
357 197
291 1
64 1
136 1
135 1
495 1
376 357
164 136
155 357
303 136
434 324
97 291
77 357
237 1
275 135
88 495
321 237
177 164
175 1
413 177
453 1
107 291
48 453
210 136
244 136
361 324
457 324
447 1
95 97
442 324
404 1
262 1
19 1
37 262
8 321
287 1
421 447
25 107
41 35...

output:

18
30
49
26
40
47
35
18
27
37
48
32
24
27
41
25
31
21
38
7
37
29
27
52
33
50
40
49
46
24
45
22
34
39
38
4
42
23
21
44
11
39
13
21
41
40
19
21
36
7
33
33
23
31
23
27
29
17
29
46
48
29
31
30
7
52
31
25
34
19
44
29
29
30
21
29
38
35
16
32
24
38
55
25
23
17
31
40
41
48
37
41
18
45
34
29
33
25
18
25
24
7...

result:

ok 100000 lines

Test #5:

score: 5
Accepted
time: 66ms
memory: 36476kb

input:

500 499 100000
186 1
155 1
450 186
265 1
201 186
286 450
210 1
486 1
475 450
331 201
158 1
239 286
355 239
378 475
22 1
156 486
452 355
87 378
360 450
27 1
73 87
474 155
322 186
148 1
112 378
332 286
269 73
102 148
163 1
341 1
98 1
402 286
138 73
347 1
33 22
467 269
326 322
462 27
258 22
216 341
174...

output:

47
63
15
45
10
32
19
10
38
27
41
5
50
40
31
9
32
13
47
41
23
25
9
57
17
45
35
28
37
18
33
14
13
22
16
27
24
16
18
49
53
35
49
22
46
58
27
42
41
31
47
6
26
48
33
33
23
51
6
34
44
46
36
35
37
46
31
24
41
13
20
30
29
31
34
33
43
23
24
37
30
30
39
15
28
38
27
42
30
13
11
55
60
17
37
38
38
51
17
30
24
49...

result:

ok 100000 lines

Test #6:

score: 5
Accepted
time: 61ms
memory: 36452kb

input:

500 499 100000
385 1
417 1
253 385
453 1
138 453
380 417
418 453
494 453
111 1
54 380
192 385
478 1
400 138
198 1
188 1
497 417
369 54
217 1
123 188
86 1
471 418
184 478
36 497
235 380
481 184
145 478
60 111
155 478
449 54
15 1
466 123
260 494
68 466
39 478
177 188
265 478
316 380
233 400
84 39
58 1...

output:

12
27
32
15
29
27
33
22
17
25
23
36
32
23
23
11
17
21
18
24
21
29
40
36
16
29
34
44
15
23
15
22
22
17
34
22
21
15
23
38
22
32
18
20
25
26
22
37
46
33
8
26
5
12
11
52
29
23
7
29
29
32
34
31
22
40
28
27
20
41
37
26
19
18
11
23
34
26
37
12
29
9
26
30
16
28
20
18
24
17
11
20
35
26
31
32
25
22
31
23
35
1...

result:

ok 100000 lines

Test #7:

score: 5
Accepted
time: 187ms
memory: 40684kb

input:

3000 100000 100000
2801 1
2606 1
697 1
1475 1
724 697
800 1
1103 2606
1123 1475
111 724
1749 724
2270 1749
2033 1
907 1
811 2033
1430 1749
1249 2606
2998 2033
2248 1
1333 1475
543 1
713 1475
2199 1
1319 811
988 1
538 1
145 1249
2082 800
2338 988
2948 1
2897 1
2487 2033
2528 1475
2859 988
1534 1249
2...

output:

53
77
83
70
51
78
68
45
65
62
60
78
89
62
49
99
111
76
107
92
31
55
85
98
135
103
48
120
78
64
140
61
69
66
102
89
100
92
127
102
12
69
107
43
66
80
52
72
86
55
96
54
57
83
58
57
83
122
70
66
76
95
55
95
93
89
70
108
74
100
79
64
88
80
49
22
94
105
83
38
122
111
71
94
73
80
80
60
7
111
87
139
92
64
...

result:

ok 100000 lines

Test #8:

score: 5
Accepted
time: 182ms
memory: 38676kb

input:

3000 100000 100000
2653 1
238 1
1585 1
2085 1
235 1
1285 1
2763 1285
759 1
1968 1585
750 1
1961 1285
2126 1
689 2763
675 2126
2282 238
2423 1285
477 2282
820 2126
2194 1
1978 1
131 2763
2705 2085
2274 759
2473 1285
2210 750
1140 2705
1687 2705
2407 820
168 689
2991 2473
2678 675
2728 1978
718 2194
2...

output:

93
131
78
96
60
142
85
72
59
88
82
137
91
126
54
63
83
77
114
126
71
69
55
124
102
114
90
72
90
106
82
100
65
61
91
107
114
131
81
79
94
65
68
89
87
85
61
53
79
68
72
97
69
115
72
54
71
97
125
68
39
75
83
94
54
114
83
75
124
104
97
126
86
103
74
87
91
64
71
70
69
95
111
108
88
146
101
117
52
88
58
3...

result:

ok 100000 lines

Test #9:

score: 5
Accepted
time: 176ms
memory: 46620kb

input:

3000 100000 100000
2465 1
1002 1
2599 1
592 2599
1078 1002
1502 1002
260 2599
2959 1
723 592
461 1
1810 723
725 2959
2410 1
2430 1
812 461
2273 260
1931 1
2663 2410
596 2273
2400 596
1461 2599
742 2959
220 812
2233 725
2419 1
187 725
888 812
437 725
2326 888
1905 461
1063 2599
1963 1
61 888
2925 190...

output:

99
53
92
91
43
94
119
58
101
94
70
110
83
126
88
64
83
116
62
107
127
113
118
97
144
84
136
100
99
104
41
116
48
103
95
67
148
71
126
79
109
108
123
65
128
107
68
83
77
88
85
95
122
117
98
123
111
105
107
130
91
74
54
114
80
55
112
89
60
84
92
69
109
110
83
125
114
84
128
116
116
106
113
121
95
145
...

result:

ok 100000 lines

Test #10:

score: 5
Accepted
time: 186ms
memory: 40672kb

input:

3000 100000 100000
2562 1
1531 1
499 2562
2027 1
1411 2562
457 1
626 2562
1449 1
2241 1
2160 1
602 457
793 1
2429 499
775 1
785 1
2227 1
443 2227
431 1411
180 457
307 2241
2659 1
1828 1449
2167 626
319 2227
2216 307
1638 2027
1208 1
407 307
1817 626
2771 1
1070 2429
545 2027
213 2659
915 2771
2275 7...

output:

72
132
99
55
92
44
52
82
95
39
65
76
70
78
158
89
101
115
76
59
102
79
74
99
56
73
102
107
72
97
122
85
37
95
91
95
99
88
35
69
55
116
79
82
117
51
100
123
105
140
75
89
89
98
148
101
94
96
85
89
93
85
88
73
50
104
86
104
99
89
92
77
127
62
81
110
122
74
83
61
98
74
89
105
88
116
133
110
89
120
86
1...

result:

ok 100000 lines

Test #11:

score: 5
Accepted
time: 185ms
memory: 42684kb

input:

3000 100000 100000
1769 1
907 1769
158 1
249 907
2958 907
221 1
2824 1
2043 221
1695 158
185 1
2765 2043
1205 249
2347 249
324 907
407 158
1286 1
330 2347
528 221
818 2958
1652 185
2870 158
2983 907
2659 1
2036 1
2007 1
237 2824
1868 2824
2278 324
1510 2347
2622 249
13 185
79 2622
1777 2007
1882 237...

output:

97
92
83
129
55
107
91
57
176
84
57
83
72
95
98
101
115
98
78
89
103
106
86
96
98
107
88
125
99
98
57
70
56
82
71
48
80
72
83
52
82
107
55
98
103
56
93
108
99
91
83
86
160
100
113
121
88
119
73
68
108
124
149
122
96
112
142
48
89
108
76
103
93
107
115
104
117
77
67
86
99
97
71
84
71
88
60
60
60
101
...

result:

ok 100000 lines

Test #12:

score: 5
Accepted
time: 184ms
memory: 38644kb

input:

3000 100000 100000
739 1
1570 1
848 1
983 739
20 1
283 1
1317 1
2965 20
571 1
2630 2965
2316 739
441 1
2113 1
2186 571
337 2630
1679 283
1086 337
586 1
1974 739
1744 2630
602 283
2401 2186
1042 1974
1711 1
13 1
1328 2186
2188 1
2031 1317
2224 337
2456 283
1140 441
269 2456
1347 2186
2531 1
350 1
110...

output:

45
61
53
92
124
50
77
81
80
81
93
58
85
75
70
70
74
123
75
134
64
92
124
99
107
111
65
69
88
110
66
99
97
88
82
84
92
101
82
58
72
119
71
99
96
86
50
81
103
85
99
66
104
89
63
80
118
48
103
96
55
82
67
90
101
101
91
51
109
123
86
161
67
91
125
89
74
74
89
76
57
47
83
45
72
97
102
63
94
55
93
90
102
...

result:

ok 100000 lines

Test #13:

score: 5
Accepted
time: 442ms
memory: 64988kb

input:

100000 99999 100000
37717 1
13239 37717
23774 13239
65149 23774
87196 65149
85561 87196
85225 85561
74026 85225
58973 74026
86179 58973
29039 86179
14547 29039
34753 14547
70013 34753
80215 70013
56494 80215
93298 56494
88017 93298
79434 88017
89466 79434
98753 89466
76439 98753
91115 76439
31702 91...

output:

1499980732
610469778
734720750
623667597
323654314
320330777
403182506
346256055
722908506
363977774
539919417
137143492
385664271
761739529
107794607
444854093
1121384634
957107856
253369752
329540852
575781055
626138721
203047807
906296473
888187646
1205383487
1482399195
634887027
714583228
771715...

result:

ok 100000 lines

Test #14:

score: 5
Accepted
time: 412ms
memory: 64896kb

input:

100000 99999 100000
68976 1
83564 68976
90392 83564
30833 90392
95920 30833
96468 95920
73543 96468
94499 73543
60701 94499
98177 60701
89037 98177
93001 89037
89810 93001
90225 89810
25665 90225
90128 25665
92458 90128
1294 92458
76926 1294
48169 76926
65677 48169
99571 65677
76577 99571
98772 7657...

output:

1499998303
956157798
31962907
161019369
1187753323
151960215
1063282765
827859604
511613343
1071110640
980026692
336107239
45350976
947674446
262083432
864639335
110865227
400474938
286648987
175875630
95965062
238934546
108436036
220701644
619360572
1120397141
821617082
380641226
739434262
18382374...

result:

ok 100000 lines

Test #15:

score: 5
Accepted
time: 432ms
memory: 64904kb

input:

100000 99999 100000
61480 1
84880 61480
78372 84880
33551 78372
90754 33551
33275 90754
15797 33275
92568 15797
91721 92568
19691 91721
4291 19691
98466 4291
29507 98466
21415 29507
87193 21415
99427 87193
86121 99427
32730 86121
96098 32730
14431 96098
52427 14431
97784 52427
96928 97784
81960 9692...

output:

1499983106
1090597018
116469304
404212666
227117627
1052003265
945299570
254190286
938832603
584246450
906709809
784960075
84018199
982275249
862885875
847986843
207037482
829317085
403503637
653710549
694434092
1145238335
462864952
834820610
1004988239
140669709
159864028
227592520
304293285
788378...

result:

ok 100000 lines

Test #16:

score: 5
Accepted
time: 443ms
memory: 64812kb

input:

100000 99999 100000
43960 1
38220 43960
45776 38220
79737 45776
54432 79737
89457 54432
19014 89457
99085 19014
26253 99085
46208 26253
96758 46208
55661 96758
94258 55661
61881 94258
70231 61881
80932 70231
80117 80932
91875 80117
77088 91875
50036 77088
90461 50036
91708 90461
63415 91708
85301 63...

output:

1499985480
455503717
1094140523
597464219
336155691
89359354
90057612
1024771299
1072838041
489473927
910333837
54542142
556422461
192921790
604938657
241573712
963140078
342098941
625331968
301729744
124475844
365679929
1156863151
30026151
13972444
96386338
232820470
513886309
990976684
180136660
7...

result:

ok 100000 lines

Test #17:

score: 5
Accepted
time: 371ms
memory: 64868kb

input:

100000 99999 100000
81972 1
85410 81972
97851 85410
63169 97851
14736 63169
79509 14736
51742 79509
94770 51742
88366 94770
37140 88366
36347 37140
99955 36347
71914 99955
68393 71914
72165 68393
75982 72165
41496 75982
50037 41496
47348 50037
65502 47348
38198 65502
92438 38198
99885 92438
34073 99...

output:

2399970283
50876
1558580872
467893128
1840057534
250879286
1850313844
736340068
731657563
1107653187
227317980
1961929
180145653
771084173
258188995
324660139
95467654
421486060
1168655916
1355663183
611971656
1369100995
1496164562
853677240
805251296
1070936259
1062819339
835112020
340663051
108177...

result:

ok 100000 lines

Test #18:

score: 5
Accepted
time: 407ms
memory: 64768kb

input:

100000 99999 100000
99170 1
76546 99170
96752 76546
80032 96752
94190 80032
16292 94190
87178 16292
99355 87178
95481 99355
59799 95481
29433 59799
36980 29433
83084 36980
63961 83084
66031 63961
75695 66031
20401 75695
65759 20401
68224 65759
74986 68224
81396 74986
99584 81396
85959 99584
75810 85...

output:

2399987854
312545277
568362996
1969603381
827352944
176750094
1099879774
1471037082
700651947
946897966
1598864688
1269336758
1140147108
1498281798
240422345
1127609156
890381661
1568660796
1554890700
770300325
758893364
168263629
1314972095
728386200
1671671177
330621006
167679079
1754358587
137128...

result:

ok 100000 lines

Test #19:

score: 5
Accepted
time: 392ms
memory: 65056kb

input:

100000 99999 100000
69928 1
61832 69928
64960 61832
61151 64960
89098 61151
34673 89098
51787 34673
99054 51787
70405 99054
98495 70405
79825 98495
21192 79825
48047 21192
71587 48047
94659 71587
67450 94659
30338 67450
72377 30338
74980 72377
61362 74980
92833 61362
66588 92833
92591 66588
84799 92...

output:

2399972657
978884974
1624231981
1356251849
675407048
441951843
1015798869
1493138267
272312548
633443576
821829079
1887591107
444772284
535992611
1387954201
1616643459
171666034
1397249259
854050051
815689655
1670236614
2325398227
1766238892
61192961
1111398410
76155614
1726044790
1708380414
8825673...

result:

ok 100000 lines

Test #20:

score: 5
Accepted
time: 391ms
memory: 64808kb

input:

100000 99999 100000
78038 1
67094 78038
87807 67094
91944 87807
10719 91944
24466 10719
61447 24466
95880 61447
85591 95880
47781 85591
71037 47781
12788 71037
91475 12788
89264 91475
33812 89264
99153 33812
69343 99153
70875 69343
77495 70875
96997 77495
46474 96997
79729 46474
95545 79729
83971 95...

output:

2399990228
904661262
840328103
326839201
5849831
1053427008
756178694
1116326914
1557908166
241240627
1935038720
509355051
1175884347
1091676432
2261484034
689660597
472933972
546006955
631277533
48139422
423820309
956981617
666313606
1148335384
1908835675
774531396
751544995
328315212
708551074
247...

result:

ok 100000 lines