QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#259932#7749. A Simple MST Problemucup-team1547TL 438ms62688kbC++232.0kb2023-11-21 16:21:132023-11-22 20:19:26

详细

Test #1:

score: 100
Accepted
time: 46ms
memory: 28444kb

input:

5
1 1
4 5
1 4
1 9
19 810

output:

0
2
3
9
1812

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 54ms
memory: 30652kb

input:

2
27 30
183704 252609

output:

8
223092

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 56ms
memory: 30768kb

input:

1
183704 252609

output:

223092

result:

ok single line: '223092'

Test #4:

score: 0
Accepted
time: 100ms
memory: 39664kb

input:

2
639898 942309
30927 34660

output:

983228
11512

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 89ms
memory: 40872kb

input:

3
21731 33468
46192 370315
1712 3753

output:

34608
948775
5299

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 62ms
memory: 31080kb

input:

4
15237 67700
10918 86104
98287 116980
17432 23592

output:

148811
210927
60893
18687

result:

ok 4 lines

Test #7:

score: 0
Accepted
time: 135ms
memory: 43852kb

input:

5
5594 70302
19202 69588
5634 7877
59821 469300
97439 261121

output:

179735
145706
6565
1203684
488669

result:

ok 5 lines

Test #8:

score: 0
Accepted
time: 115ms
memory: 35348kb

input:

6
43477 229639
188276 269887
72424 150178
9009 36918
137421 180271
14666 124530

output:

541705
255651
232054
77284
135277
313203

result:

ok 6 lines

Test #9:

score: 0
Accepted
time: 88ms
memory: 34652kb

input:

7
461436 501798
98856 148334
20953 119408
910 5027
762 14117
10959 46088
96149 130311

output:

139017
151124
281536
10504
34818
98004
108375

result:

ok 7 lines

Test #10:

score: 0
Accepted
time: 114ms
memory: 36296kb

input:

8
6448 11162
33691 94044
137536 140277
106719 267437
13494 38185
3185 4173
4835 299526
25162 43201

output:

13177
175485
9711
480992
69059
2808
840950
53422

result:

ok 8 lines

Test #11:

score: 0
Accepted
time: 96ms
memory: 32596kb

input:

9
4136 54985
38425 155322
107602 157683
115533 137627
13677 44903
43432 69310
70004 129314
43033 55373
76424 147123

output:

139668
339337
153266
68520
87592
76612
183238
39109
211339

result:

ok 9 lines

Test #12:

score: 0
Accepted
time: 108ms
memory: 35224kb

input:

10
21662 27103
55634 196143
20466 44902
87028 202799
127745 151602
1598 1679
95299 126981
13367 134183
52307 66285
10136 38071

output:

17117
410126
71979
344673
74754
263
100586
342577
41870
77522

result:

ok 10 lines

Test #13:

score: 0
Accepted
time: 97ms
memory: 34328kb

input:

20
14973 29525
12674 35281
27500 64458
67431 109122
12468 19466
4606 9884
38731 44161
3212 89277
23213 37134
4392 40769
5378 7211
22586 29237
56331 81369
43924 59554
31787 34990
19949 21972
47309 65085
5666 48185
99 2714
7969 131566

output:

40882
63073
107649
129480
19975
14563
17562
238237
41056
99346
5358
20747
73854
48244
9911
6517
54866
117382
6374
347901

result:

ok 20 lines

Test #14:

score: 0
Accepted
time: 81ms
memory: 30576kb

input:

30
11101 53557
6079 6241
869 14433
6164 10602
73432 82272
15845 17496
18885 49518
12127 35037
5812 14898
12225 15757
19736 36027
34506 69210
12204 37099
642 1256
11875 12382
169453 211949
20884 26173
8302 26634
75302 79147
13938 16896
11229 13736
4753 7575
2742 17752
4443 5021
2988 5533
1042 1364
19...

output:

118619
538
35473
12392
28768
4915
88426
63728
25217
10666
47893
102086
69488
1584
1669
135374
16581
50701
12720
8517
7762
8170
40235
1798
7014
936
78143
29
32461
19423

result:

ok 30 lines

Test #15:

score: 0
Accepted
time: 114ms
memory: 31580kb

input:

40
1022 1378
14032 55415
12506 15792
3919 16767
12870 32763
10624 12091
1144 29449
5184 9133
4178 8021
7785 13966
3880 26749
15390 34240
2582 11246
431 4695
7020 28894
14092 27156
52666 55295
4068 22068
7392 11533
18273 31481
18854 47481
7786 39812
7341 24968
22021 54790
3221 10332
4930 37633
4407 1...

output:

959
116367
9946
34920
55460
4626
75707
10961
11069
17829
62128
52987
23362
10769
60198
36594
9093
48818
11976
39528
82591
88609
48598
96601
19475
89551
19435
27135
16967
139445
1063
181709
57729
6335
4114
5586
5189
5669
59793
8451

result:

ok 40 lines

Test #16:

score: 0
Accepted
time: 108ms
memory: 33124kb

input:

50
15626 23807
5585 6016
6101 8103
9127 21310
36189 45079
14069 28358
4793 6034
4029 8938
35309 95923
43860 65991
3472 11896
13230 36032
11979 20636
2432 24320
1680 8915
2612 5242
9797 10319
2232 9531
24754 30470
41799 71066
9681 10551
434 2733
8898 28848
2033 35179
8338 13387
1547 5093
1840 3757
47...

output:

23466
1386
5889
33690
28343
40048
3754
13493
176378
65680
23137
63701
24080
59083
18974
7221
1739
19409
17905
86553
2807
5709
55079
89488
15241
9203
4985
12067
5112
815
36773
6032
21936
48301
14796
43205
40728
1000
10389
346
16233
134
5168
54990
5999
25607
7930
9444
25040
30739

result:

ok 50 lines

Test #17:

score: 0
Accepted
time: 97ms
memory: 31388kb

input:

60
1284 4788
3389 36000
222 7286
25716 33186
38085 40233
3531 6181
774 2555
2653 3785
1441 2911
5474 6951
7325 8378
623 1484
3626 29205
863 14748
49190 61921
2406 35177
7742 9801
200 1071
5199 13189
7551 9135
25991 50726
17330 21478
46 97
1580 6205
7679 16145
7074 19995
17354 41321
7546 9420
3186 71...

output:

9024
88511
17924
22330
7191
7459
4538
3287
3846
4320
3130
2162
69268
36338
39569
88635
5995
2088
22192
4684
73244
12692
112
12062
23979
35542
68915
5472
10740
464
301
171
1183
29157
16502
38047
16131
3142
4940
51225
10426
4988
20823
38873
1185
31126
665
11014
128
9270
4447
12193
22928
10020
521
5876...

result:

ok 60 lines

Test #18:

score: 0
Accepted
time: 93ms
memory: 30164kb

input:

70
2967 4866
39014 52178
4501 9931
2868 17671
18883 24548
44427 53286
9239 37925
1019 1411
234 3511
4974 11964
3336 7079
2397 2807
1482 5860
845 967
47 3347
22581 38595
618 9784
1987 6683
1970 10280
13073 16008
12155 23980
26996 33533
1211 2524
116 3464
292 360
342 432
10396 22134
21754 66962
10977 ...

output:

5260
41323
14979
39729
17180
28404
79481
1059
8102
19420
10197
1225
11392
373
8086
47200
23657
12336
21966
8903
32960
19601
3385
8239
193
250
32568
131030
41881
26631
57583
18937
22825
27887
7666
45760
37714
4084
1599
7021
13489
3750
22270
13773
686
10747
2711
1325
15075
206
12399
28434
14321
5809
1...

result:

ok 70 lines

Test #19:

score: 0
Accepted
time: 102ms
memory: 32732kb

input:

80
227 762
1864 11313
3710 6984
9210 16876
2146 5715
12841 17952
540 3928
2471 3084
1297 10323
1336 4968
2550 2572
33143 35415
821 1994
1397 14292
6850 16209
9375 15494
829 4086
6431 26191
20951 28745
3738 19999
101 4288
2971 5562
809 1230
21199 26540
181 386
11348 11762
2783 5152
17773 39328
2469 3...

output:

1273
25013
8944
21618
9356
14607
8548
1852
23539
9384
74
7598
3126
34097
26366
18382
8268
54251
24042
43950
10390
7142
1132
16776
486
1397
6513
61971
2251
2716
119
10648
11149
14387
88616
48016
3101
13598
42354
15386
761
11212
11013
15564
4022
23786
18860
39658
2971
20321
9970
65802
3429
2772
19206
...

result:

ok 80 lines

Test #20:

score: 0
Accepted
time: 94ms
memory: 30560kb

input:

90
1834 3251
1286 4017
968 8098
991 1889
4679 9273
47 2565
404 3201
1698 5864
1568 3560
2090 4761
5519 20863
952 1123
6765 7477
1881 12407
22889 32445
1149 1341
5532 20827
2641 11993
4531 5449
1440 16324
2378 29912
10725 14148
913 1665
3757 3940
2607 6438
663 1609
1134 19991
7011 7315
3043 4479
1183...

output:

3678
7004
18415
2406
12675
6103
6973
10872
5155
7008
41935
469
2265
27853
29404
566
41797
25248
2792
39305
74142
10472
2013
597
10541
2425
49947
1026
3977
1732
21450
11809
1816
1175
21684
176
24632
13337
2393
3679
145481
1240
1203
34363
15259
26644
14236
8201
5876
432
18294
211
1018
2099
28005
33979...

result:

ok 90 lines

Test #21:

score: 0
Accepted
time: 95ms
memory: 31152kb

input:

100
2851 7328
280 359
20953 49433
106 1188
195 208
5208 9395
8380 12027
8091 11163
3161 7447
215 3448
2022 7980
4069 7320
2838 3679
15 231
1888 14353
10452 12414
4 1185
789 1675
19521 23307
301 2895
6831 30967
33555 35031
483 2712
4746 21571
4294 13075
13819 13959
5986 15296
9258 9513
331 6202
2467 ...

output:

12003
221
83960
2553
41
11627
11086
8930
11682
7983
15657
8920
2482
466
33116
6113
2741
2360
11587
6407
66138
4987
5539
45716
24197
479
25858
866
14840
7126
11092
15742
1357
59273
7251
95126
5877
9720
19666
59359
3213
5286
7653
2305
8616
3020
718
7748
3928
6874
27620
0
23370
10227
7369
4750
59084
55...

result:

ok 100 lines

Test #22:

score: 0
Accepted
time: 99ms
memory: 29352kb

input:

500
2771 3702
817 1288
1215 5937
453 1488
3267 3321
2058 2466
703 825
9 97
1251 2046
234 1684
4778 7026
2763 5165
11 32
620 1738
367 1281
2469 5782
650 5733
138 479
1879 3268
124 1307
2795 3892
2069 3176
6336 7230
1176 2018
324 1422
1596 3589
680 1487
1904 2126
16 27
620 1118
52 215
4143 4516
511 62...

output:

2723
1266
12164
2574
187
1172
345
180
2286
3513
6500
6601
42
2812
2276
9095
12945
805
3613
2825
3197
3054
2672
2410
2667
5162
2069
630
22
1255
361
1194
295
7685
7555
1503
94
247
4141
6957
4296
558
20
8633
8501
5076
464
5344
13145
3032
2471
3
3203
1477
353
1084
4158
3948
755
4821
15
6213
2893
69
7032...

result:

ok 500 lines

Test #23:

score: 0
Accepted
time: 118ms
memory: 28396kb

input:

1000
932 1194
499 1287
611 956
9 21
664 1391
952 1557
907 2348
577 1235
50 75
106 118
142 145
1571 1936
389 1759
42 220
1185 2020
84 148
269 583
1041 1075
132 364
326 2104
230 351
241 1473
503 651
139 144
272 316
619 1996
199 276
77 1302
1205 3722
57 683
519 2892
283 723
1406 1827
271 1232
134 1804
...

output:

713
1972
932
24
1858
1620
3720
1658
60
35
11
1078
3411
389
2394
151
791
113
542
4369
291
2970
385
16
132
3475
188
2896
6435
1438
5915
1091
1244
2326
4015
914
852
924
287
11
1517
238
308
244
3637
290
370
2144
2024
3977
355
3676
1499
1010
484
87
52
120
2346
5153
331
92
75
1753
34
909
753
384
695
1109
...

result:

ok 1000 lines

Test #24:

score: 0
Accepted
time: 281ms
memory: 29540kb

input:

5000
70 106
5 7
212 380
2 2
371 820
1 332
120 279
158 213
49 310
1 312
695 778
112 116
81 264
13 63
51 104
32 62
29 37
16 117
181 233
126 1433
276 548
5 108
26 220
278 330
307 367
69 573
22 36
713 717
29 171
7 72
312 337
59 188
2 12
38 445
14 235
32 44
460 652
329 436
51 231
191 238
38 67
168 221
30...

output:

93
5
401
0
1112
646
362
154
579
604
239
13
412
102
119
68
19
211
146
3113
685
209
420
153
168
1151
29
18
306
130
75
286
17
915
477
28
497
297
401
133
67
149
853
130
827
346
0
168
298
521
331
25
307
21
47
112
216
736
84
211
399
4
485
115
85
175
9
143
185
1
23
5
87
71
237
1424
24
359
152
9
202
72
476
...

result:

ok 5000 lines

Test #25:

score: 0
Accepted
time: 406ms
memory: 28044kb

input:

10000
108 274
1 18
1 1
10 16
5 68
11 25
54 202
5 11
4 15
10 56
1 1
10 19
54 164
58 60
45 189
38 49
22 36
66 115
30 79
52 77
66 73
172 322
101 133
40 167
93 94
30 49
93 218
4 6
57 63
11 32
76 77
197 223
28 31
3 4
17 74
6 6
29 31
72 174
57 60
75 79
30 32
138 172
118 126
5 8
31 45
7 132
20 98
7 30
12 1...

output:

378
23
0
13
124
29
327
12
21
93
0
19
242
7
313
30
29
124
111
60
20
361
78
274
4
43
295
4
18
42
4
76
9
2
118
0
6
227
10
13
5
96
24
6
33
257
162
45
6
2
199
69
25
11
10
112
22
21
44
0
20
389
0
42
49
2
68
115
112
164
4
22
0
31
11
115
81
618
147
43
0
384
36
12
302
48
136
71
0
13
43
15
54
30
24
73
136
35
...

result:

ok 10000 lines

Test #26:

score: 0
Accepted
time: 438ms
memory: 28804kb

input:

20000
41 43
13 18
52 83
7 21
2 4
13 117
9 12
1 20
29 37
13 18
14 51
1 98
6 7
6 9
8 38
70 70
1 2
29 64
27 28
2 3
2 3
106 144
25 45
13 17
12 41
19 38
17 29
13 23
155 190
52 123
10 11
2 7
25 62
2 2
5 65
2 5
15 191
1 2
77 77
4 4
1 8
65 86
110 248
2 10
4 7
1 77
3 33
6 17
28 51
22 67
2 37
2 2
4 6
20 27
4 ...

output:

6
11
69
27
3
217
7
26
19
11
75
167
3
6
58
0
1
78
3
2
2
91
42
9
58
39
27
22
100
159
3
9
77
0
117
5
376
1
0
0
8
55
314
13
6
127
55
21
52
93
64
0
4
16
6
45
15
5
2
104
10
46
1
107
301
45
20
25
72
0
75
6
40
28
167
44
2
2
18
3
70
38
1
60
9
26
2
0
31
14
149
3
3
80
167
405
27
17
0
162
14
7
15
20
3
25
34
6
7...

result:

ok 20000 lines

Test #27:

score: 0
Accepted
time: 367ms
memory: 28900kb

input:

30000
2 9
6 9
7 16
28 69
3 7
1 5
1 1
1 3
29 30
2 2
4 5
1 42
13 62
5 15
1 6
15 34
9 45
10 63
7 10
2 2
7 11
113 143
6 6
1 1
17 48
26 52
4 4
43 66
111 133
3 5
11 32
2 2
24 58
1 1
10 58
3 3
5 26
4 16
9 22
1 4
45 48
26 28
27 36
35 54
28 101
10 22
1 2
2 4
1 1
5 14
31 52
6 13
21 31
17 23
7 48
21 38
3 65
2 ...

output:

11
6
17
93
8
4
0
2
4
0
2
64
100
20
6
38
72
108
6
0
8
73
0
0
64
54
0
53
55
4
42
0
70
0
97
0
40
22
26
3
9
6
20
48
157
26
1
3
0
18
47
14
24
16
81
35
119
19
9
6
28
9
0
52
12
102
6
25
85
0
12
27
85
56
27
7
36
25
0
14
14
0
8
39
6
55
33
2
2
18
0
182
17
28
2
19
143
6
39
4
44
17
72
32
4
12
6
14
27
6
21
23
36...

result:

ok 30000 lines

Test #28:

score: 0
Accepted
time: 299ms
memory: 29184kb

input:

40000
5 11
1 3
3 23
12 19
28 29
2 3
9 20
6 8
2 3
2 4
13 19
5 16
8 14
16 23
5 20
3 9
10 12
20 23
10 10
40 69
8 9
9 50
11 14
4 10
13 15
5 21
2 11
2 14
6 16
19 52
8 20
5 5
2 4
18 20
6 39
12 25
1 3
40 122
12 87
5 11
1 13
35 38
6 7
22 38
20 21
2 33
39 59
21 29
2 28
7 7
23 23
38 40
2 6
1 1
59 83
41 57
10 ...

output:

12
2
37
15
3
2
22
4
2
3
13
21
12
15
29
10
6
9
0
67
2
82
8
11
6
31
15
21
19
68
23
0
3
6
64
27
2
180
154
12
15
9
3
33
4
56
52
19
46
0
0
7
7
0
54
42
8
0
93
58
5
12
143
91
0
13
16
1
9
14
1
3
3
11
3
47
3
19
65
34
5
75
27
17
2
33
15
0
9
17
0
24
105
28
21
31
0
12
41
2
26
171
4
11
13
2
25
18
0
21
29
108
0
3...

result:

ok 40000 lines

Test #29:

score: 0
Accepted
time: 248ms
memory: 27772kb

input:

50000
3 7
11 12
22 24
9 18
9 57
1 2
3 11
6 7
16 21
12 31
11 18
12 13
6 17
8 15
5 20
3 7
5 10
10 14
3 6
2 3
2 3
3 6
2 6
4 4
1 7
7 7
8 15
1 14
4 4
4 22
17 17
3 25
8 12
36 77
1 1
9 9
17 25
16 18
1 12
38 46
11 20
19 40
1 26
14 16
8 60
30 31
4 7
8 10
3 9
8 18
19 29
1 1
6 7
11 12
1 5
13 37
10 40
33 71
44 ...

output:

8
3
6
18
96
1
14
3
11
39
15
3
21
14
29
8
10
11
6
2
2
6
7
0
7
0
14
17
0
34
0
40
8
93
0
0
19
4
14
24
19
43
36
5
104
4
6
4
10
19
23
0
3
3
4
48
60
88
61
6
11
21
7
43
12
0
5
26
0
0
18
9
23
7
0
15
29
2
2
8
0
3
1
2
19
8
63
62
29
46
64
24
78
0
0
8
3
6
14
0
6
24
0
8
8
0
14
2
5
3
4
0
14
68
3
3
60
35
44
31
40
...

result:

ok 50000 lines

Test #30:

score: 0
Accepted
time: 48ms
memory: 29032kb

input:

10
99860 99870
99872 99876
99882 99900
99902 99906
99908 99922
99924 99928
99930 99960
99962 99970
99972 99988
99992 100002

output:

43
18
79
21
62
18
128
39
66
41

result:

ok 10 lines

Test #31:

score: 0
Accepted
time: 47ms
memory: 29264kb

input:

412
54 58
74 78
84 88
90 96
114 120
132 136
140 148
152 156
158 162
174 178
182 190
200 210
212 222
234 238
244 250
258 262
264 268
272 276
284 288
294 306
318 330
332 336
338 342
354 358
362 366
368 372
374 378
384 388
390 396
402 408
410 418
422 430
434 438
444 448
450 456
468 478
480 486
492 498
...

output:

13
15
15
20
23
15
27
16
13
15
30
35
34
16
21
16
16
16
15
43
41
15
16
16
16
16
16
14
24
24
30
30
17
15
24
38
21
25
16
27
16
38
16
30
17
15
15
30
16
17
16
17
16
17
28
15
16
39
18
24
30
24
31
23
16
24
16
21
46
30
38
32
30
37
42
67
24
30
25
17
18
24
17
14
16
29
16
38
16
20
20
30
30
20
60
18
17
25
19
15
...

result:

ok 412 lines

Test #32:

score: 0
Accepted
time: 47ms
memory: 29676kb

input:

2
492114 492227
492157 492227

output:

447
275

result:

ok 2 lines

Test #33:

score: 0
Accepted
time: 135ms
memory: 62688kb

input:

1
1 1000000

output:

2853708

result:

ok single line: '2853708'

Test #34:

score: 0
Accepted
time: 166ms
memory: 57852kb

input:

5
1 2
2 3
114514 999990
3 4
1 1

output:

1
2
2652563
2
0

result:

ok 5 lines

Test #35:

score: 0
Accepted
time: 164ms
memory: 59056kb

input:

10
3 14
15 926
535 897
9 32
3 84
626 43383
2 7
950 21145
141 919810
20 1210

output:

20
2097
970
45
160
115330
9
53450
2691545
2780

result:

ok 10 lines

Extra Test:

score: -3
Extra Test Failed : Time Limit Exceeded on 3

input:

8849
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2 113
2...

output:

223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
223
...

result: