QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#524658	#1142. Fountain Parks	Mousa_Aboubaker^#	15	620ms	78388kb	C++20	5.6kb	2024-08-19 22:38:42	2024-08-19 22:38:43

Judging History

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

[2024-08-19 22:38:43]
评测

测评结果：15
用时：620ms
内存：78388kb

查看

[2024-08-19 22:38:42]
提交

answer

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

int construct_roads(std::vector<int> x, std::vector<int> y)
{
    map<pair<int, int>, int> found, vis;
    for (int i = 0; i < x.size(); i++)
    {
        found[{x[i], y[i]}] = i;
    }
    queue<pair<int, int>> q;
    q.push({x[0], y[0]});
    vector<int> u, v, a, b;
    while (!q.empty())
    {
        auto [x1, y1] = q.front();
        q.pop();

        if (vis[{x1, y1}])
        {
            continue;
        }

        vis[{x1, y1}] = true;
        // up nightbour
        if (found[{x1, y1 + 2}] and !vis[{x1, y1 + 2}])
        {
            if (x1 == 2)
            {
                if (!vis[{x1 - 1, y1 + 1}])
                {
                    u.push_back(found[{x1, y1}]);
                    v.push_back(found[{x1, y1 + 2}]);
                    a.push_back(x1 - 1);
                    b.push_back(y1 + 1);
                    q.push({x1, y1 + 2});
                    vis[{x1 - 1, y1 + 1}] = true;
                }
                else if (!vis[{x1 + 1, y1 + 1}])
                {
                    u.push_back(found[{x1, y1}]);
                    v.push_back(found[{x1, y1 + 2}]);
                    a.push_back(x1 + 1);
                    b.push_back(y1 + 1);
                    q.push({x1, y1 + 2});
                    vis[{x1 + 1, y1 + 1}] = true;
                }
            }
            else
            {

                if (!vis[{x1 + 1, y1 + 1}])
                {
                    u.push_back(found[{x1, y1}]);
                    v.push_back(found[{x1, y1 + 2}]);
                    a.push_back(x1 + 1);
                    b.push_back(y1 + 1);
                    q.push({x1, y1 + 2});
                    vis[{x1 + 1, y1 + 1}] = true;
                }
                else if (!vis[{x1 - 1, y1 + 1}])
                {
                    u.push_back(found[{x1, y1}]);
                    v.push_back(found[{x1, y1 + 2}]);
                    a.push_back(x1 - 1);
                    b.push_back(y1 + 1);
                    q.push({x1, y1 + 2});
                    vis[{x1 - 1, y1 + 1}] = true;
                }
            }
        }

        // down nightbour
        if (found[{x1, y1 - 2}] and !vis[{x1, y1 - 2}])
        {
            if (x1 == 2)
            {
                if (!vis[{x1 - 1, y1 - 1}])
                {
                    u.push_back(found[{x1, y1}]);
                    v.push_back(found[{x1, y1 - 2}]);
                    a.push_back(x1 - 1);
                    b.push_back(y1 - 1);
                    q.push({x1, y1 - 2});
                    vis[{x1 - 1, y1 - 1}] = true;
                }
                else if (!vis[{x1 + 1, y1 - 1}])
                {
                    u.push_back(found[{x1, y1}]);
                    v.push_back(found[{x1, y1 - 2}]);
                    a.push_back(x1 + 1);
                    b.push_back(y1 - 1);
                    q.push({x1, y1 - 2});
                    vis[{x1 + 1, y1 - 1}] = true;
                }
            }
            else
            {

                if (!vis[{x1 + 1, y1 - 1}])
                {
                    u.push_back(found[{x1, y1}]);
                    v.push_back(found[{x1, y1 - 2}]);
                    a.push_back(x1 + 1);
                    b.push_back(y1 - 1);
                    q.push({x1, y1 - 2});
                    vis[{x1 + 1, y1 - 1}] = true;
                }
                else if (!vis[{x1 - 1, y1 - 1}])
                {
                    u.push_back(found[{x1, y1}]);
                    v.push_back(found[{x1, y1 - 2}]);
                    a.push_back(x1 - 1);
                    b.push_back(y1 - 1);
                    q.push({x1, y1 - 2});
                    vis[{x1 - 1, y1 - 1}] = true;
                }
            }
        }

        // right nighbour
        if (found[{x1 + 2, y1}] and !vis[{x1 + 2, y1}])
        {
            if (!vis[{x1 + 1, y1 - 1}])
            {
                u.push_back(found[{x1, y1}]);
                v.push_back(found[{x1 + 2, y1}]);
                a.push_back(x1 + 1);
                b.push_back(y1 - 1);
                q.push({x1 + 2, y1});
                vis[{x1 + 1, y1 - 1}] = true;
            }
            else if (!vis[{x1 - 1, y1 - 1}])
            {
                u.push_back(found[{x1, y1}]);
                v.push_back(found[{x1 + 2, y1}]);
                a.push_back(x1 - 1);
                b.push_back(y1 - 1);
                q.push({x1 + 2, y1});
                vis[{x1 - 1, y1 - 1}] = true;
            }
        }

        // left nightbour
        if (found[{x1 - 2, y1}] and !vis[{x1 - 2, y1}])
        {
            if (!vis[{x1 - 1, y1 - 1}])
            {
                u.push_back(found[{x1, y1}]);
                v.push_back(found[{x1 - 2, y1}]);
                a.push_back(x1 - 1);
                b.push_back(y1 - 1);
                q.push({x1 - 2, y1});
                vis[{x1 - 1, y1 - 1}] = true;
            }
            else if (!vis[{x1 + 1, y1 - 1}])
            {
                u.push_back(found[{x1, y1}]);
                v.push_back(found[{x1 - 2, y1}]);
                a.push_back(x1 + 1);
                b.push_back(y1 - 1);
                q.push({x1 - 2, y1});
                vis[{x1 + 1, y1 - 1}] = true;
            }
        }
    }

    if (u.size() < x.size() - 1)
    {
        return 0;
    }

    build(u, v, a, b);
    return 1;
}
// void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 0ms

memory: 3800kb

input:

ba73dbf9c7d5e5202834d6a500541c
1
2 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
0

result:

ok

Test #2:

score: 5

Accepted

time: 0ms

memory: 4076kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
2 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1
0 1 1 3

result:

ok

Test #3:

score: 5

Accepted

time: 0ms

memory: 3792kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
2 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #4:

score: 5

Accepted

time: 0ms

memory: 3884kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
2 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 1 3
1 2 1 5

result:

ok

Test #5:

score: 5

Accepted

time: 0ms

memory: 4040kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 2
2 4
2 6
2 8

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
3
0 1 1 3
1 2 1 5
2 3 1 7

result:

ok

Test #6:

score: 5

Accepted

time: 0ms

memory: 3784kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
2 8

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #7:

score: 5

Accepted

time: 0ms

memory: 3792kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 2
2 4
2 8
2 10

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #8:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 2
2 4
2 6
2 10

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #9:

score: 5

Accepted

time: 237ms

memory: 40760kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
2 15660
2 23918
2 132200
2 117654
2 162750
2 183010
2 75554
2 29740
2 185476
2 135138
2 194024
2 182274
2 1338
2 42922
2 51616
2 171196
2 159598
2 136432
2 84454
2 61806
2 136968
2 167442
2 150036
2 23974
2 10064
2 86342
2 146274
2 174318
2 130832
2 118838
2 180...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 86548 1 15661
0 30345 1 15659
86548 51470 1 15663
30345 82179 1 15657
51470 3650 1 15665
82179 64823 1 15655
3650 64744 1 15667
64823 86081 1 15653
64744 31576 1 15669
86081 27849 1 15651
31576 88961 1 15671
27849 1420 1 15649
88961 56176 1 15673...

result:

ok

Test #10:

score: 5

Accepted

time: 16ms

memory: 7400kb

input:

ba73dbf9c7d5e5202834d6a500541c
10000
2 3124
2 3126
2 3128
2 3130
2 3132
2 3134
2 3136
2 3138
2 3140
2 3142
2 3144
2 3146
2 3148
2 3150
2 3152
2 3154
2 3156
2 3158
2 3160
2 3162
2 3164
2 3166
2 3168
2 3170
2 3172
2 3174
2 3176
2 3178
2 3180
2 3182
2 3184
2 3186
2 3188
2 3190
2 3192
2 3194
2 3196
2 31...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
9999
0 1 1 3125
1 2 1 3127
2 3 1 3129
3 4 1 3131
4 5 1 3133
5 6 1 3135
6 7 1 3137
7 8 1 3139
8 9 1 3141
9 10 1 3143
10 11 1 3145
11 12 1 3147
12 13 1 3149
13 14 1 3151
14 15 1 3153
15 16 1 3155
16 17 1 3157
17 18 1 3159
18 19 1 3161
19 20 1 3163
20 21 1 ...

result:

ok

Test #11:

score: 5

Accepted

time: 112ms

memory: 23600kb

input:

ba73dbf9c7d5e5202834d6a500541c
53891
2 3566
2 3568
2 3570
2 3572
2 3574
2 3576
2 3578
2 3580
2 3582
2 3584
2 3586
2 3588
2 3590
2 3592
2 3594
2 3596
2 3598
2 3600
2 3602
2 3604
2 3606
2 3608
2 3610
2 3612
2 3614
2 3616
2 3618
2 3620
2 3622
2 3624
2 3626
2 3628
2 3630
2 3632
2 3634
2 3636
2 3638
2 36...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
53890
0 1 1 3567
1 2 1 3569
2 3 1 3571
3 4 1 3573
4 5 1 3575
5 6 1 3577
6 7 1 3579
7 8 1 3581
8 9 1 3583
9 10 1 3585
10 11 1 3587
11 12 1 3589
12 13 1 3591
13 14 1 3593
14 15 1 3595
15 16 1 3597
16 17 1 3599
17 18 1 3601
18 19 1 3603
19 20 1 3605
20 21 1...

result:

ok

Test #12:

score: 5

Accepted

time: 25ms

memory: 9028kb

input:

ba73dbf9c7d5e5202834d6a500541c
14979
2 4954
2 4956
2 4958
2 4960
2 4962
2 4964
2 4966
2 4968
2 4970
2 4972
2 4974
2 4976
2 4978
2 4980
2 4982
2 4984
2 4986
2 4988
2 4990
2 4992
2 4994
2 4996
2 4998
2 5000
2 5002
2 5004
2 5006
2 5008
2 5010
2 5012
2 5014
2 5016
2 5018
2 5020
2 5022
2 5024
2 5026
2 50...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
14978
0 1 1 4955
1 2 1 4957
2 3 1 4959
3 4 1 4961
4 5 1 4963
5 6 1 4965
6 7 1 4967
7 8 1 4969
8 9 1 4971
9 10 1 4973
10 11 1 4975
11 12 1 4977
12 13 1 4979
13 14 1 4981
14 15 1 4983
15 16 1 4985
16 17 1 4987
17 18 1 4989
18 19 1 4991
19 20 1 4993
20 21 1...

result:

ok

Test #13:

score: 5

Accepted

time: 51ms

memory: 14728kb

input:

ba73dbf9c7d5e5202834d6a500541c
44171
2 36500
2 36502
2 36504
2 36506
2 36508
2 36510
2 36512
2 36514
2 36516
2 36518
2 36520
2 36522
2 36524
2 36526
2 36528
2 36530
2 36532
2 36534
2 36536
2 36538
2 36540
2 36542
2 36544
2 36546
2 36548
2 36550
2 36552
2 36554
2 36556
2 36558
2 36560
2 36562
2 36564...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #14:

score: 5

Accepted

time: 1ms

memory: 3996kb

input:

ba73dbf9c7d5e5202834d6a500541c
1000
2 20406
2 20378
2 37840
2 37702
2 20448
2 37688
2 37780
2 20720
2 38256
2 20612
2 38050
2 20152
2 37880
2 20116
2 20030
2 20526
2 38324
2 20956
2 20852
2 20356
2 37668
2 20292
2 37648
2 20320
2 20078
2 38060
2 38014
2 37738
2 37878
2 20336
2 20472
2 20214
2 38340
...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #15:

score: 5

Accepted

time: 1ms

memory: 4380kb

input:

ba73dbf9c7d5e5202834d6a500541c
2000
2 19578
2 1754
2 1760
2 130946
2 164378
2 1038
2 20302
2 131788
2 131632
2 164392
2 19868
2 164924
2 131380
2 130972
2 131348
2 1070
2 131568
2 19492
2 19876
2 131606
2 1142
2 1588
2 1424
2 1726
2 131416
2 946
2 20158
2 19574
2 20106
2 1736
2 1186
2 19476
2 164256...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #16:

score: 5

Accepted

time: 247ms

memory: 40636kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
2 103034
2 75068
2 69976
2 84860
2 113488
2 156808
2 109250
2 119184
2 169250
2 182382
2 161594
2 169232
2 41046
2 87158
2 10192
2 32612
2 84228
2 49708
2 157912
2 160028
2 160234
2 167142
2 22010
2 37360
2 64100
2 113388
2 81460
2 52862
2 77902
2 155958
2 13330...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 21451 1 103035
0 22204 1 103033
21451 29258 1 103037
22204 82343 1 103031
29258 67648 1 103039
82343 29285 1 103029
67648 76589 1 103041
29285 55421 1 103027
76589 85459 1 103043
55421 42442 1 103025
85459 49020 1 103045
42442 96204 1 103023
4902...

result:

ok

Subtask #2:

score: 10

Accepted

Dependency #1:

100%

Accepted

Test #17:

score: 10

Accepted

time: 0ms

memory: 3792kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
4 4
2 4
4 2
2 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
4
0 2 5 3
0 1 3 3
2 3 3 1
1 3 1 3

result:

ok

Test #18:

score: 10

Accepted

time: 0ms

memory: 3788kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
4 4
2 6
2 4
4 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
4
0 3 5 5
0 2 3 3
3 1 3 5
2 1 1 5

result:

ok

Test #19:

score: 10

Accepted

time: 0ms

memory: 3816kb

input:

ba73dbf9c7d5e5202834d6a500541c
6
4 6
2 4
2 2
4 2
4 4
2 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
7
0 4 5 5
0 5 3 5
4 3 5 3
4 1 3 3
5 1 1 5
3 2 3 1
1 2 1 3

result:

ok

Test #20:

score: 10

Accepted

time: 0ms

memory: 4072kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
4 2
2 6
4 8
2 4
4 6
2 2
4 4
2 8

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
10
0 6 5 3
0 5 3 1
6 4 5 5
6 3 3 3
5 3 1 3
4 2 5 7
4 1 3 5
3 1 1 5
2 7 3 7
1 7 1 7

result:

ok

Test #21:

score: 10

Accepted

time: 0ms

memory: 3808kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
2 10
2 4
4 4
4 8
2 2
2 8
4 10
4 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #22:

score: 10

Accepted

time: 0ms

memory: 3812kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 200000
4 199998
2 199998
4 200000

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
4
0 2 1 199999
0 3 3 199999
2 1 3 199997
3 1 5 199999

result:

ok

Test #23:

score: 10

Accepted

time: 591ms

memory: 76752kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
4 177614
4 159166
2 99950
4 127824
2 158654
4 82678
2 76278
2 198694
4 142000
4 8782
2 49352
2 71260
2 194790
2 87904
2 70702
2 20966
4 161326
2 52586
2 18108
2 36098
2 160702
2 102232
2 67042
2 16712
2 141944
4 27120
4 43282
4 139388
2 144766
4 75542
4 5228
2 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
299998
0 59080 5 177615
0 76079 5 177613
0 184307 3 177613
59080 29517 5 177617
59080 21090 3 177615
76079 114331 5 177611
76079 176199 3 177611
184307 21090 1 177615
184307 176199 1 177613
29517 29641 5 177619
29517 78631 3 177617
21090 78631 1 177617
1...

result:

ok

Test #24:

score: 10

Accepted

time: 0ms

memory: 3884kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
2 183570
4 183570
4 183572
2 183572
2 183578
4 183574
2 183576
4 183576

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
8
0 3 1 183571
0 1 3 183569
3 2 3 183571
1 2 5 183571
2 5 5 183573
5 7 5 183575
7 6 3 183575
6 4 1 183577

result:

ok

Test #25:

score: 10

Accepted

time: 2ms

memory: 4384kb

input:

ba73dbf9c7d5e5202834d6a500541c
1173
2 186526
2 185928
4 185842
4 185780
4 185692
4 186148
4 186016
2 186236
4 185948
4 185626
2 186332
4 186206
2 186480
4 186154
2 186542
2 186504
2 186230
2 186654
2 185902
4 186762
4 186074
2 185804
4 186262
4 185834
2 186224
4 186544
4 185604
2 186300
2 186042
4 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1757
0 585 1 186527
0 43 1 186525
0 729 3 186525
585 591 1 186529
585 569 3 186527
43 150 1 186523
43 1165 3 186523
729 569 5 186527
729 1165 5 186525
591 940 1 186531
591 911 3 186529
569 911 5 186529
150 663 1 186521
150 597 3 186521
1165 597 5 186523
...

result:

ok

Test #26:

score: 10

Accepted

time: 3ms

memory: 4504kb

input:

ba73dbf9c7d5e5202834d6a500541c
3000
2 109002
2 197108
4 198220
4 197488
4 108286
2 109006
2 197954
2 108586
4 197416
4 197132
4 197374
4 197448
4 197898
2 108330
2 197992
4 109556
2 197598
4 108114
4 109046
2 197128
2 108454
2 108892
2 108110
4 108622
4 197756
2 197924
2 109102
2 198050
2 108460
2 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #27:

score: 10

Accepted

time: 2ms

memory: 4300kb

input:

ba73dbf9c7d5e5202834d6a500541c
4000
2 140462
2 140478
2 140596
2 4466
2 172072
2 140272
4 64560
2 64340
4 172244
4 64230
2 57126
4 158866
2 140482
2 64878
4 159028
4 140276
2 56814
2 4364
2 64356
4 64834
4 57096
2 3922
2 172124
4 64542
2 159218
4 140762
2 172112
4 140320
4 56964
4 158988
4 140398
2 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #28:

score: 10

Accepted

time: 197ms

memory: 32524kb

input:

ba73dbf9c7d5e5202834d6a500541c
80000
2 77930
2 34884
4 40062
2 34158
2 6130
4 32544
2 51290
2 50478
4 70072
4 69616
2 75800
4 5656
2 4510
2 77766
2 68358
2 42792
4 52374
4 48488
2 75616
2 46682
4 45386
4 28842
2 12918
4 8206
2 20568
2 70466
2 5562
4 61202
2 65046
4 71854
4 9510
2 45910
2 14066
4 608...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
119998
0 13711 1 77931
0 23775 1 77929
0 79027 3 77929
13711 29858 1 77933
13711 64819 3 77931
23775 50410 1 77927
23775 18058 3 77927
79027 64819 5 77931
79027 18058 5 77929
29858 61647 1 77935
29858 46063 3 77933
64819 46063 5 77933
50410 5967 1 77925
...

result:

ok

Test #29:

score: 10

Accepted

time: 325ms

memory: 47496kb

input:

ba73dbf9c7d5e5202834d6a500541c
120000
2 107882
4 86012
4 127996
2 176868
2 178032
4 122930
4 178436
4 160026
4 152606
2 160512
2 84884
2 161726
4 190586
2 149048
2 131608
2 80390
2 155598
4 84696
2 182976
4 158014
4 173998
2 159392
4 128890
4 119618
4 196866
2 97962
4 188404
2 133252
4 166790
4 1593...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
179997
0 30090 1 107883
0 112528 1 107881
0 42961 3 107881
30090 41117 1 107885
30090 10508 3 107883
112528 99479 1 107879
112528 56616 3 107879
42961 10508 5 107883
42961 56616 5 107881
41117 64833 1 107887
41117 55056 3 107885
10508 55056 5 107885
9947...

result:

ok

Test #30:

score: 10

Accepted

time: 439ms

memory: 62028kb

input:

ba73dbf9c7d5e5202834d6a500541c
160000
2 52858
4 164410
2 75528
2 52886
4 109942
4 170460
2 186328
2 124554
4 197478
2 192650
4 78512
4 153868
4 155132
2 162316
4 122256
2 166830
2 163464
2 129030
4 191906
4 68290
4 64288
4 152134
4 79376
2 125460
4 51150
2 106656
4 139088
2 136352
2 52620
4 95892
2 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
239998
0 30042 1 52859
0 137867 1 52857
0 146571 3 52857
30042 123706 1 52861
30042 10544 3 52859
137867 90762 1 52855
137867 57501 3 52855
146571 10544 5 52859
146571 57501 5 52857
123706 154349 1 52863
123706 86276 3 52861
10544 86276 5 52861
90762 153...

result:

ok

Test #31:

score: 10

Accepted

time: 620ms

memory: 76772kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
4 159176
4 173814
4 148140
4 192932
2 10458
4 82176
2 192792
4 58608
4 152072
2 179396
4 65044
2 43890
2 6200
4 72634
2 27580
2 178602
2 61556
4 157146
2 133400
4 126376
4 18694
2 195536
4 159494
4 84034
2 33830
4 92734
2 6522
4 109768
2 101402
4 6176
4 53030
2 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
299998
0 40413 5 159177
0 51331 5 159175
0 12274 3 159175
40413 17386 5 159179
40413 164171 3 159177
51331 131392 5 159173
51331 33130 3 159173
12274 164171 1 159177
12274 33130 1 159175
17386 38642 5 159181
17386 47301 3 159179
164171 47301 1 159179
131...

result:

ok

Test #32:

score: 10

Accepted

time: 1ms

memory: 3784kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
4 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1
0 1 5 3

result:

ok

Test #33:

score: 10

Accepted

time: 0ms

memory: 3780kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
4 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1
0 1 3 1

result:

ok

Test #34:

score: 10

Accepted

time: 0ms

memory: 4068kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 4
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1
0 1 3 3

result:

ok

Test #35:

score: 10

Accepted

time: 0ms

memory: 3784kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #36:

score: 10

Accepted

time: 0ms

memory: 3788kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 4
4 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #37:

score: 10

Accepted

time: 0ms

memory: 4040kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
4 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 1 3
0 2 3 1

result:

ok

Test #38:

score: 10

Accepted

time: 0ms

memory: 4004kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 1 3
1 2 3 3

result:

ok

Test #39:

score: 10

Accepted

time: 0ms

memory: 3736kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
4 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 3 1
1 2 5 3

result:

ok

Test #40:

score: 10

Accepted

time: 0ms

memory: 3776kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 4
4 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 2 3 3
2 1 5 3

result:

ok

Test #41:

score: 10

Accepted

time: 0ms

memory: 3804kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 4
4 2
4 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #42:

score: 10

Accepted

time: 0ms

memory: 3780kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 200000
2 199998
4 200000

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 1 199999
0 2 3 199999

result:

ok

Test #43:

score: 10

Accepted

time: 2ms

memory: 4100kb

input:

ba73dbf9c7d5e5202834d6a500541c
2000
2 66072
2 15600
2 65278
2 65372
2 15154
2 64698
4 15472
4 15336
4 15714
4 65714
2 65516
4 65552
2 64890
2 15174
2 65674
2 14732
2 15150
4 65768
2 15672
2 14610
4 15530
2 65776
2 15370
4 65724
2 15308
2 15412
4 15712
4 14620
4 14600
2 15404
4 15918
2 14858
2 15488
...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #44:

score: 10

Accepted

time: 2ms

memory: 4448kb

input:

ba73dbf9c7d5e5202834d6a500541c
3000
2 111548
2 111040
4 70070
2 177612
2 110868
2 111368
4 17940
2 111432
2 59736
2 177494
4 110958
2 70064
2 59920
2 70092
4 177672
2 59336
4 69988
4 111040
2 59840
4 18638
4 18042
2 111192
2 177526
4 69992
4 177776
4 69676
4 177824
4 111128
4 111278
4 59162
2 111592...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #45:

score: 10

Accepted

time: 206ms

memory: 36824kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
4 169676
2 166424
4 184362
4 189372
4 92358
4 163106
4 106516
4 84160
2 80238
2 189392
4 195840
2 118396
4 94344
4 188728
2 189284
2 164532
2 140524
2 126720
4 182624
4 131538
2 172512
2 163134
2 123156
4 137156
4 168310
2 140776
4 181764
2 92658
2 124148
4 1125...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 31285 5 169677
0 57741 5 169675
31285 74285 3 169677
57741 62423 3 169673
74285 40662 1 169679
62423 75710 1 169673
40662 38512 1 169681
75710 91161 1 169671
38512 78163 1 169683
38512 3850 3 169681
91161 44986 3 169669
78163 32096 1 169685
44986...

result:

ok

Test #46:

score: 10

Accepted

time: 334ms

memory: 52024kb

input:

ba73dbf9c7d5e5202834d6a500541c
145093
2 166114
2 57160
2 100318
2 183710
2 157582
4 87300
2 108292
4 26942
4 152146
4 67878
2 189520
2 105504
4 182488
4 20028
4 149088
2 27528
4 54250
2 100720
2 62956
4 60756
2 107208
4 156884
2 184558
2 79524
4 152584
4 101220
2 8320
4 149952
4 2512
4 63280
2 14975...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
145092
0 134467 1 166115
0 17095 3 166113
134467 119920 1 166117
17095 43862 5 166113
119920 25896 1 166119
43862 64206 5 166111
25896 15516 3 166119
64206 8896 5 166109
15516 139836 5 166121
8896 141760 5 166107
8896 117050 3 166107
139836 121549 5 1661...

result:

ok

Test #47:

score: 10

Accepted

time: 333ms

memory: 52060kb

input:

ba73dbf9c7d5e5202834d6a500541c
145075
2 155250
2 136442
2 94908
2 158406
4 57086
2 97650
4 48200
2 12782
2 185128
2 197282
4 27270
2 122262
4 66214
2 31156
2 150590
2 12294
4 1562
4 94584
2 23458
4 157278
4 33026
2 191138
4 147538
2 8652
2 108482
4 67498
4 157020
2 13190
2 30028
4 77576
4 44258
4 16...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
145074
0 64143 1 155251
0 63781 3 155249
64143 2843 1 155253
63781 64793 5 155249
2843 69322 3 155253
64793 68128 5 155247
69322 60388 5 155255
68128 9297 5 155245
60388 36810 5 155257
9297 122732 5 155243
9297 63178 3 155243
36810 124439 5 155259
122732...

result:

ok

Subtask #3:

score: 0

Wrong Answer

Dependency #2:

100%

Accepted

Test #48:

score: 15

Accepted

time: 0ms

memory: 4084kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
6 2
4 2
6 4
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
4
0 2 7 3
0 1 5 1
2 3 5 3
1 3 3 3

result:

ok

Test #49:

score: 15

Accepted

time: 0ms

memory: 4036kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
6 6
4 4
6 4
4 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
4
0 2 7 5
0 3 5 5
2 1 5 3
3 1 3 5

result:

ok

Test #50:

score: 15

Accepted

time: 0ms

memory: 4076kb

input:

ba73dbf9c7d5e5202834d6a500541c
6
6 2
2 2
6 4
2 4
4 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
6
0 2 7 3
0 4 5 1
2 5 5 3
4 5 3 3
4 1 3 1
1 3 1 3

result:

ok

Test #51:

score: 15

Accepted

time: 0ms

memory: 3788kb

input:

ba73dbf9c7d5e5202834d6a500541c
7
6 4
4 4
2 2
4 6
4 2
2 4
6 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
7
0 6 7 5
0 1 5 3
6 3 5 5
1 3 3 5
1 4 3 3
4 2 3 1
2 5 1 3

result:

ok

Test #52:

score: 0

Wrong Answer

time: 0ms

memory: 3808kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
4 2
2 2
6 8
4 6
4 8
4 4
6 6
2 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
9
0 5 5 3
0 1 3 1
5 3 5 5
5 7 3 3
1 7 1 3
3 4 5 7
3 6 3 5
4 2 3 7
6 2 7 7

result:

wrong answer Tree (a[6], b[6]) = (3, 5) is not adjacent to edge between u[6]=3 @(4, 6) and v[6]=6 @(6, 6)

Subtask #4:

score: 0

Wrong Answer

Test #82:

score: 20

Accepted

time: 0ms

memory: 3788kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
200000 2
200000 4
199998 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 200001 3
0 2 199999 1

result:

ok

Test #83:

score: 20

Accepted

time: 0ms

memory: 4072kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
200000 200000
200000 199998
199998 200000

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 200001 199999
0 2 199999 199999

result:

ok

Test #84:

score: 20

Accepted

time: 0ms

memory: 4084kb

input:

ba73dbf9c7d5e5202834d6a500541c
12
2 2
2 4
4 2
2 200000
2 199998
4 200000
200000 2
200000 4
199998 2
200000 200000
200000 199998
199998 200000

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok

Test #85:

score: 20

Accepted

time: 423ms

memory: 65604kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
195232 4772
192370 7632
64282 135722
174444 25558
54846 145156
70170 129832
196228 3774
23234 176768
186862 13140
22458 177546
18158 181846
144902 55100
109692 90310
154220 45782
180406 19598
176744 23260
69098 130906
83308 116694
728 199274
143272 56730
17012 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 114192 195233 4771
0 183397 195231 4771
114192 40149 195233 4769
183397 25518 195231 4773
40149 199945 195235 4769
25518 169400 195229 4773
199945 1522 195235 4767
169400 147022 195229 4775
1522 130824 195237 4767
147022 151960 195227 4775
13082...

result:

ok

Test #86:

score: 0

Wrong Answer

time: 447ms

memory: 65608kb

input:

ba73dbf9c7d5e5202834d6a500541c
199997
56858 56864
1456 1462
51406 51410
89266 89272
53562 53556
80164 80158
13970 13966
41960 41966
48338 48342
98766 98772
82904 82898
38168 38172
28780 28774
38142 38146
16616 16612
15258 15262
69676 69672
85410 85416
59306 59310
712 718
6144 6140
61280 61286
28928 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199996
0 178618 56859 56863
0 69117 56857 56863
178618 54764 56857 56861
69117 63811 56861 56865
54764 71838 56855 56861
63811 193897 56859 56865
71838 166678 56855 56859
193897 184833 56863 56867
166678 36870 56853 56859
184833 43499 56861 56867
36870 2...

result:

wrong answer Tree (a[1], b[1]) = (56857, 56863) is not adjacent to edge between u[1]=0 @(56858, 56864) and v[1]=69117 @(56860, 56864)

Subtask #5:

score: 0

Wrong Answer

Test #108:

score: 20

Accepted

time: 533ms

memory: 78360kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
82422 100002
100002 52498
82816 2
97624 2
100002 58032
20638 100002
100002 7646
80512 2
2 10584
28426 100002
2 83036
2 64556
47872 100002
55196 2
85350 100002
2 95376
2 23942
12488 100002
83178 2
2 9086
85598 2
100002 78820
100002 10868
98810 2
84182 100002
2 71...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
200000
0 168975 82423 100001
0 148989 82421 100001
168975 129862 82425 100001
148989 138668 82419 100001
129862 183101 82427 100001
138668 25843 82417 100001
183101 20766 82429 100001
25843 187856 82415 100001
20766 71258 82431 100001
187856 176130 82413...

result:

ok

Test #109:

score: 0

Wrong Answer

time: 511ms

memory: 78388kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
10674 50002
7228 2
31566 50002
48790 2
87212 50002
100002 76172
54282 100002
2 33136
100002 78564
50002 9882
50848 50002
50002 83692
92422 100002
100002 78880
100002 71432
50002 65586
3750 2
50002 11898
50002 17296
50002 44774
3836 2
49936 50002
50002 48536
1542...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199999
0 113011 10675 50001
0 28598 10673 50001
113011 4917 10677 50001
28598 195343 10671 50001
4917 133766 10679 50001
195343 30065 10669 50001
133766 177889 10681 50001
30065 64561 10667 50001
177889 51243 10683 50001
64561 88066 10665 50001
51243 102...

result:

wrong answer Tree (a[114328], b[114328]) = (50001, 100001) is not adjacent to edge between u[114328]=112203 @(50002, 100002) and v[114328]=107366 @(50004, 100002)

Subtask #6:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted