QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#852845#9733. Heavy-light Decompositionucup-team4478#AC ✓20ms7700kbC++142.8kb2025-01-11 14:23:252025-01-11 14:23:34

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5476kb

input:

3
12 5
1 5
9 11
7 8
6 6
12 12
4 3
1 1
4 4
2 3
2 2
1 1
2 2

output:

0 1 2 3 4 1 1 7 1 9 10 1
2 0 2 2
IMPOSSIBLE

result:

ok Correct. (3 test cases)

Test #2:

score: 0
Accepted
time: 2ms
memory: 6344kb

input:

10
1 1
1 1
100000 1
1 100000
12 4
1 3
4 6
7 9
10 12
6 3
4 6
2 3
1 1
8999 3
1 3000
3001 6000
6001 8999
14 4
1 3
4 6
7 10
11 14
17 5
1 3
4 6
7 10
11 14
15 17
19999 2
1 9999
10000 19999
1 1
1 1
5 3
1 1
2 3
4 5

output:

0
0 1 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

ok Correct. (10 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 6016kb

input:

5
11 5
1 3
4 6
7 8
9 10
11 11
39998 4
1 10000
10001 20000
20001 30000
30001 39998
49000 5
1 10000
39999 49000
10001 20000
20001 30000
30001 39998
16 5
1 1
2 3
4 6
7 11
12 16
10 5
1 2
3 4
5 6
7 8
9 10

output:

0 1 2 1 4 5 1 7 1 9 2
0 1 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 ...

result:

ok Correct. (5 test cases)

Test #4:

score: 0
Accepted
time: 12ms
memory: 5700kb

input:

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

output:

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

result:

ok Correct. (10000 test cases)

Test #5:

score: 0
Accepted
time: 13ms
memory: 5708kb

input:

20000
13 12
12 12
7 7
1 1
5 5
9 9
8 8
13 13
4 4
3 3
6 6
10 11
2 2
16 8
4 4
5 5
1 1
6 6
7 7
3 3
8 16
2 2
20 17
19 19
1 1
17 18
14 14
4 4
13 13
7 7
5 5
11 11
15 15
16 16
20 20
12 12
9 10
8 8
2 3
6 6
17 9
3 4
2 2
9 10
7 8
5 6
11 12
1 1
15 17
13 14
6 2
2 6
1 1
1 1
1 1
10 2
5 10
1 4
17 17
3 3
12 12
15 15...

output:

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

result:

ok Correct. (20000 test cases)

Test #6:

score: 0
Accepted
time: 13ms
memory: 5540kb

input:

50000
1 1
1 1
4 3
1 1
4 4
2 3
9 9
1 1
5 5
8 8
9 9
7 7
2 2
3 3
6 6
4 4
4 2
1 2
3 4
2 2
1 1
2 2
1 1
1 1
10 2
1 7
8 10
8 8
4 4
5 5
6 6
8 8
3 3
1 1
2 2
7 7
7 7
7 7
4 4
5 5
2 2
3 3
1 1
6 6
10 2
8 10
1 7
8 1
1 8
2 1
1 2
9 4
1 2
5 6
7 9
3 4
7 1
1 7
7 2
1 1
2 7
4 2
1 1
2 4
6 3
3 6
1 1
2 2
3 3
3 3
1 1
2 2
1 ...

output:

0
2 0 2 2
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
0
0 1 2 3 4 5 6 1 8 9
IMPOSSIBLE
IMPOSSIBLE
0 1 2 3 4 5 6 1 8 9
0 1 2 3 4 5 6 7
0 1
7 1 7 3 7 5 0 7 8
0 1 2 3 4 5 6
2 0 2 3 4 5 6
2 0 2 3
3 3 0 3 4 5
IMPOSSIBLE
0
3 3 0 3
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
0 1
IMPOSSIBLE
0 1 1 1
3 3 0 3 3
IMPOSSIBL...

result:

ok Correct. (50000 test cases)

Test #7:

score: 0
Accepted
time: 9ms
memory: 5804kb

input:

100
2619 693
286 286
81 81
552 552
397 397
24 24
414 414
378 378
660 660
538 538
125 125
190 190
585 585
180 180
564 564
218 218
158 158
425 425
189 189
94 94
29 29
678 678
543 543
352 352
659 659
467 467
403 403
298 298
517 517
196 196
156 156
278 278
259 259
417 417
499 499
246 246
195 195
380 380...

output:

693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 ...

result:

ok Correct. (100 test cases)

Test #8:

score: 0
Accepted
time: 11ms
memory: 6928kb

input:

100
53984 965
9577 9632
53593 53648
17305 17360
40321 40376
37465 37520
45753 45808
52921 52976
21281 21336
44241 44296
17921 17976
40545 40600
7897 7952
9689 9744
32089 32144
43345 43400
46817 46872
4817 4872
24585 24640
41889 41944
36065 36120
3585 3640
1486 1540
29793 29848
8065 8120
43401 43456
...

output:

IMPOSSIBLE
IMPOSSIBLE
35753 1 2 3 4 5 35753 35753 8 35753 10 11 12 13 35753 35753 35753 35753 18 35753 35753 35753 22 35753 35753 35753 35753 35753 35753 29 30 35753 32 35753 35753 35 36 35753 35753 39 40 41 42 43 44 45 46 47 35753 49 35753 35753 35753 35753 54 55 56 35753 58 59 35753 35753 62 63 64...

result:

ok Correct. (100 test cases)

Test #9:

score: 0
Accepted
time: 15ms
memory: 6808kb

input:

2
100000 72281
52926 52926
1645 1646
33266 33266
88480 88480
16983 16983
29975 29977
32528 32528
89186 89186
5810 5810
90512 90512
8859 8859
22671 22671
51648 51649
26506 26506
99017 99018
64526 64526
61453 61454
73914 73914
27338 27339
43510 43510
22298 22300
59714 59714
64394 64395
71955 71956
481...

output:

25150 25150 2 3 25150 25150 25150 7 25150 25150 10 11 25150 25150 25150 25150 16 25150 18 19 20 25150 25150 23 24 25150 26 25150 25150 25150 25150 25150 25150 25150 25150 25150 36 25150 38 39 25150 25150 25150 25150 25150 45 25150 47 25150 49 50 25150 25150 25150 25150 25150 25150 25150 25150 25150 ...

result:

ok Correct. (2 test cases)

Test #10:

score: 0
Accepted
time: 20ms
memory: 5648kb

input:

100000
2 1
1 2
2 1
1 2
2 2
2 2
1 1
2 2
2 2
1 1
2 2
1 1
2 2
2 2
2 2
1 1
2 2
1 1
2 2
2 2
1 1
2 2
2 2
1 1
2 2
2 2
2 2
1 1
2 2
2 2
1 1
2 2
1 1
2 2
2 2
1 1
2 2
2 2
2 2
1 1
2 1
1 2
2 2
2 2
1 1
2 2
2 2
1 1
2 2
2 2
1 1
2 1
1 2
2 2
1 1
2 2
2 2
1 1
2 2
2 1
1 2
2 2
2 2
1 1
2 2
2 2
1 1
2 2
1 1
2 2
2 1
1 2
2 2
1...

output:

0 1
0 1
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
0 1
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
0 1
IMPOSSIBLE
IMPOSSIBLE
0 1
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
0 1
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
0...

result:

ok Correct. (100000 test cases)

Test #11:

score: 0
Accepted
time: 15ms
memory: 5604kb

input:

100000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok Correct. (100000 test cases)

Test #12:

score: 0
Accepted
time: 17ms
memory: 5704kb

input:

100000
2 1
1 2
3 1
1 3
5 2
1 1
2 5
4 4
2 2
4 4
3 3
1 1
3 3
1 1
3 3
2 2
5 1
1 5
1 1
1 1
3 2
1 1
2 3
5 5
5 5
2 2
3 3
4 4
1 1
3 3
3 3
1 1
2 2
5 4
3 4
1 1
2 2
5 5
4 3
2 2
1 1
3 4
1 1
1 1
4 1
1 4
5 4
3 4
2 2
1 1
5 5
3 1
1 3
3 3
1 1
3 3
2 2
5 1
1 5
1 1
1 1
2 2
2 2
1 1
5 1
1 5
1 1
1 1
2 2
2 2
1 1
4 2
4 4
1...

output:

0 1
0 1 2
2 0 2 3 4
IMPOSSIBLE
IMPOSSIBLE
0 1 2 3 4
0
2 0 2
IMPOSSIBLE
IMPOSSIBLE
3 3 0 3 3
3 3 0 3
0
0 1 2 3
3 3 0 3 3
0 1 2
IMPOSSIBLE
0 1 2 3 4
0
IMPOSSIBLE
0 1 2 3 4
0
IMPOSSIBLE
0 1 2 1
3 3 0 3 4
0 1 1
IMPOSSIBLE
IMPOSSIBLE
0
3 1 0 3 4
0
IMPOSSIBLE
3 3 0 3 4
0 1 2
3 3 0 3
0
0
IMPOSSIBLE
0 1 2 1...

result:

ok Correct. (100000 test cases)

Test #13:

score: 0
Accepted
time: 7ms
memory: 7616kb

input:

5000
50 26
5 6
9 10
1 1
23 24
43 44
19 20
29 30
2 2
17 18
47 48
3 4
35 36
27 28
25 26
49 50
31 32
45 46
15 16
39 40
21 22
11 12
13 14
37 38
33 34
7 8
41 42
86 12
17 20
33 36
41 86
1 3
4 6
13 16
25 28
37 40
29 32
21 24
7 9
10 12
59 35
5 5
6 6
22 22
31 31
32 32
25 25
21 21
20 20
26 26
2 2
34 34
3 3
35...

output:

IMPOSSIBLE
41 1 2 41 4 5 41 7 8 41 10 11 41 13 14 15 41 17 18 19 41 21 22 23 41 25 26 27 41 29 30 31 41 33 34 35 41 37 38 39 0 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
35 35 35 35 35 35 35 35 35 35 35 35 35...

result:

ok Correct. (5000 test cases)

Test #14:

score: 0
Accepted
time: 11ms
memory: 7536kb

input:

5000
335 22
13 18
134 140
85 91
50 56
7 12
31 36
113 119
71 77
106 112
1 6
37 42
64 70
92 98
43 49
120 126
127 133
99 105
25 30
141 335
19 24
57 63
78 84
475 21
40 42
22 24
37 39
16 18
7 9
31 33
49 51
43 45
52 54
19 21
1 2
55 57
10 12
5 6
58 475
28 30
13 15
25 27
34 36
3 4
46 48
252 159
138 138
77 7...

output:

141 1 2 3 4 5 141 7 8 9 10 11 141 13 14 15 16 17 141 19 20 21 22 23 141 25 26 27 28 29 141 31 32 33 34 35 141 37 38 39 40 41 141 43 44 45 46 47 48 141 50 51 52 53 54 55 141 57 58 59 60 61 62 141 64 65 66 67 68 69 141 71 72 73 74 75 76 141 78 79 80 81 82 83 141 85 86 87 88 89 90 141 92 93 94 95 96 97...

result:

ok Correct. (5000 test cases)

Test #15:

score: 0
Accepted
time: 12ms
memory: 7700kb

input:

1000
89 19
17 18
7 8
11 12
1 1
27 28
35 89
13 14
15 16
25 26
9 10
31 32
3 4
33 34
29 30
19 20
23 24
5 6
21 22
2 2
962 187
886 890
361 365
376 380
766 770
901 905
181 185
626 630
921 925
86 90
416 420
281 285
506 510
171 175
41 45
776 780
441 445
491 495
341 345
631 635
141 145
356 360
891 895
231 23...

output:

35 35 35 3 35 5 35 7 35 9 35 11 35 13 35 15 35 17 35 19 35 21 35 23 35 25 35 27 35 29 35 31 35 33 0 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
926 1 2 3 926 5 6 7 926 9 10 11 926 13...

result:

ok Correct. (1000 test cases)

Test #16:

score: 0
Accepted
time: 6ms
memory: 5716kb

input:

500
4037 286
1756 1768
2770 2782
3095 3107
1405 1417
2705 2717
2913 2925
1847 1859
482 494
807 819
2744 2756
2822 2834
2276 2288
3238 3250
1106 1118
2055 2067
3056 3068
2328 2340
2146 2158
1249 1261
1015 1027
2224 2236
1613 1625
1717 1729
222 234
3329 3341
1795 1807
2354 2366
37 48
3082 3094
2068 20...

output:

3693 1 2 3 4 5 6 7 8 9 10 11 3693 13 14 15 16 17 18 19 20 21 22 23 3693 25 26 27 28 29 30 31 32 33 34 35 3693 37 38 39 40 41 42 43 44 45 46 47 3693 49 50 51 52 53 54 55 56 57 58 59 3693 61 62 63 64 65 66 67 68 69 70 71 3693 73 74 75 76 77 78 79 80 81 82 83 3693 85 86 87 88 89 90 91 92 93 94 95 3693 ...

result:

ok Correct. (500 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-01-20 05:52:26 | OpenSource Project