QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292779#5706. Villagewhdywjd12 41ms164588kbC++145.4kb2023-12-28 13:07:102023-12-28 13:07:10

Judging History

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

  • [2023-12-28 13:07:10]
  • 评测
  • 测评结果：12
  • 用时：41ms
  • 内存：164588kb
查看
  • [2023-12-28 13:07:10]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define ll long long
#define lf double
#define _1 first
#define _2 second
#define _mp make_pair
#define _pb push_back
#define MAX_N 222222
#define inf 2222222222222222222ll

using namespace std;

ll read(){ll x = 0;char c = 0, v = 0;do{c = getchar();if(c == '-')v = 1;} while(c < '0' || c > '9');do{x = (x << 3) + (x << 1) + c - '0';c = getchar();} while(c >= '0' && c <= '9');return v ? -x : x;}

template<size_t N>
struct Tree
{
    int n, rt;
    vector<int> G[N];
    void build(int x, int y)
    {
        G[x]._pb(y);
        G[y]._pb(x);
        n = max(n, max(x, y));
    }

    #define Edgs(p, x, f) for(auto p: G[x]) if(p != (f))
    int SIZE, MNVAL, MNPOS;
    void Gdfs1(int x, int f)
    {
        SIZE++;
        Edgs(p, x, f)
            Gdfs1(p, x);
    }

    int Gdfs2(int x, int f)
    {
        int sz = 1, mxsz = 0;
        Edgs(p, x, f)
        {
            int d = Gdfs2(p, x);
            sz += d;
            mxsz = max(mxsz, d);
        }
        mxsz = max(mxsz, SIZE - sz);
        if(mxsz < MNVAL)
            MNVAL = mxsz, MNPOS = x;
        return sz;
    }

    int Gx()
    {
        SIZE = 0, MNVAL = N, MNPOS = 0;
        Gdfs1(1, 0), Gdfs2(1, 0);
        return MNPOS;
    }

    int sz[N];
    void dfs1(int x, int f)
    {
        sz[x] = 1;
        Edgs(p, x, f)
        {
            dfs1(p, x);
            sz[x] += sz[p];
        }
    }

    ll dp[N][2];
    int mat1[N];
    ll ans1;
    void dfs2(int x, int f)
    {
        if(sz[x] == 1)
        {
            dp[x][0] = -2 * (int)N;
            dp[x][1] = 0;
            return;
        }
        dp[x][0] = 1, dp[x][1] = 0;
        bool flag = 0;
        Edgs(p, x, f)
        {
            dfs2(p, x);
            dp[x][1] += dp[p][0];
            if(dp[p][0] > dp[p][1])
                dp[x][0] += dp[p][0];
            else
                flag = 1, dp[x][0] += dp[p][1];
        }
        if(flag)
            return;
        ll mn = N;
        Edgs(p, x, f)
            mn = min(mn, dp[p][0] - dp[p][1]);
        dp[x][0] -= mn;
    }

    void output1(int x, int f, bool sta)
    {
        //printf(" %d %d\n", x, (int)sta);
        if(sz[x] == 1)
            return;
        if(sta)
        {
            Edgs(p, x, f)
                output1(p, x, 0);
            return;
        }
        bool flag = 0;
        Edgs(p, x, f)
            if(dp[p][0] <= dp[p][1])
                flag = 1;
        if(flag)
        {
            ll lst = x;
            Edgs(p, x, f)
            {
                if(dp[p][0] > dp[p][1])
                    output1(p, x, 0);
                else
                {
                    mat1[lst] = p;
                    lst = p;
                    output1(p, x, 1);
                }
            }
            mat1[lst] = x;
            return;
        }
        ll mn = N;
        int mnp = 0;
        Edgs(p, x, f)
            if(dp[p][0] - dp[p][1] < mn)
                mn = dp[p][0] - dp[p][1], mnp = p;
        mat1[x] = mnp, mat1[mnp] = x;
        Edgs(p, x, f)
        {
            if(p == mnp)
                output1(p, x, 1);
            else
                output1(p, x, 0);
        }
    }

    int m;
    stack<int> nds[N];
    priority_queue<pair<int, int> > q; // <size, id>
    int mat2[N];
    ll ans2;
    void dfs3(int x, int f, int d, int id)
    {
        nds[id].push(x);
        ans2 += 2 * d;
        Edgs(p, x, f)
            dfs3(p, x, d + 1, id);
    }

    void main()
    {
        rt = Gx();
        //printf("%d\n", rt);
        dfs1(rt, 0);
        dfs2(rt, 0);
        ans1 = 2 * (n - dp[rt][0]);
        output1(rt, 0, 0);
        //return;
        m = ans2 = 0;
        Edgs(p, rt, 0)
        {
            m++;
            dfs3(p, rt, 1, m);
            q.push(_mp(sz[p], m));
        }
        //return;
        for(int i = 1; 2 * i < n; i++)
        {
            pair<int, int> p1 = q.top();
            q.pop();
            pair<int, int> p2 = q.top();
            q.pop();
            int x1 = nds[p1._2].top();
            nds[p1._2].pop();
            int x2 = nds[p2._2].top();
            nds[p2._2].pop();
            if(i == 1 && (n & 1))
                mat2[x1] = rt, mat2[rt] = x2, mat2[x2] = x1;
            else
                mat2[x1] = x2, mat2[x2] = x1;
            if(p1._1 > 1)
                q.push(_mp(p1._1 - 1, p1._2));
            if(p2._1 > 1)
                q.push(_mp(p2._1 - 1, p2._2));
        }
        //return;
        if(!(n & 1))
        {
            pair<int, int> p1 = q.top();
            q.pop();
            int x1 = nds[p1._2].top();
            nds[p1._2].pop();
            mat2[x1] = rt;
            mat2[rt] = x1;
        }
    }
};

Tree<MAX_N> tr;
int n;

void MAIN()
{
    n = read();
    for(int i = 1; i < n; i++)
        tr.build(read(), read());
    tr.main();
    printf("%lld %lld\n", tr.ans1, tr.ans2);
    for(int i = 1; i <= n; i++)
        printf("%d ", tr.mat1[i]);
    printf("\n");
    for(int i = 1; i <= n; i++)
        printf("%d ", tr.mat2[i]);
    printf("\n");
}

void CLEAR()
{
    ;
}

void EXP()
{
    ;
}

int main()
{
    EXP();
    int T = 1;
    while(T--)
        MAIN(), CLEAR();
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 12
Accepted

Test #1:

score: 12
Accepted
time: 24ms
memory: 161520kb

input:

4
1 2
2 3
3 4

output:

4 8
2 1 4 3 
4 3 2 1

result:

points 1.0 correct answer = 4; correct answer = 8;

Test #2:

score: 12
Accepted
time: 26ms
memory: 161708kb

input:

7
4 2
5 7
3 4
6 3
1 3
4 5

output:

8 18
3 4 6 2 7 1 5 
4 3 2 7 6 5 1

result:

points 1.0 correct answer = 8; correct answer = 18;

Test #3:

score: 12
Accepted
time: 16ms
memory: 161432kb

input:

2
1 2

output:

2 2
2 1 
2 1

result:

points 1.0 correct answer = 2; correct answer = 2;

Test #4:

score: 12
Accepted
time: 12ms
memory: 163816kb

input:

7
4 1
7 6
7 5
1 3
3 2
1 6

output:

8 20
4 3 2 6 7 1 5 
2 5 7 6 1 4 3

result:

points 1.0 correct answer = 8; correct answer = 20;

Test #5:

score: 12
Accepted
time: 19ms
memory: 164008kb

input:

7
2 7
5 2
6 1
1 4
4 5
7 3

output:

8 24
6 4 7 5 2 1 3 
7 4 6 2 3 5 1

result:

points 1.0 correct answer = 8; correct answer = 24;

Test #6:

score: 12
Accepted
time: 34ms
memory: 161428kb

input:

7
5 3
3 6
3 1
1 7
1 4
5 2

output:

8 18
7 5 6 1 2 3 4 
5 4 2 3 1 7 6

result:

points 1.0 correct answer = 8; correct answer = 18;

Test #7:

score: 12
Accepted
time: 31ms
memory: 163884kb

input:

7
7 3
4 7
1 7
7 2
5 7
7 6

output:

12 12
2 5 4 1 6 7 3 
2 1 4 3 6 7 5

result:

points 1.0 correct answer = 12; correct answer = 12;

Test #8:

score: 12
Accepted
time: 20ms
memory: 163768kb

input:

8
4 8
5 2
6 2
3 8
4 7
2 8
2 1

output:

10 22
2 5 8 7 6 1 4 3 
7 8 6 5 4 3 1 2

result:

points 1.0 correct answer = 10; correct answer = 22;

Test #9:

score: 12
Accepted
time: 27ms
memory: 163996kb

input:

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

output:

14 22
6 3 5 8 9 7 4 1 2 
3 8 1 2 6 5 9 4 7

result:

points 1.0 correct answer = 14; correct answer = 22;

Test #10:

score: 12
Accepted
time: 15ms
memory: 161516kb

input:

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

output:

10 30
3 10 1 6 7 4 5 9 8 2 
4 7 10 1 9 8 2 6 5 3

result:

points 1.0 correct answer = 10; correct answer = 30;

Test #11:

score: 12
Accepted
time: 22ms
memory: 161476kb

input:

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

output:

10 50
6 9 8 7 10 1 4 3 2 5 
7 9 10 6 8 4 1 5 2 3

result:

points 1.0 correct answer = 10; correct answer = 50;

Test #12:

score: 12
Accepted
time: 16ms
memory: 161408kb

input:

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

output:

10 42
4 7 9 1 10 8 2 6 3 5 
10 7 4 3 8 9 2 5 6 1

result:

points 1.0 correct answer = 10; correct answer = 42;

Test #13:

score: 12
Accepted
time: 31ms
memory: 161676kb

input:

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

output:

14 28
5 7 2 3 9 8 4 10 1 6 
2 1 9 5 4 10 8 7 3 6

result:

points 1.0 correct answer = 14; correct answer = 28;

Test #14:

score: 12
Accepted
time: 23ms
memory: 161436kb

input:

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

output:

18 18
2 9 8 10 6 3 1 7 4 5 
7 9 8 10 6 5 1 3 2 4

result:

points 1.0 correct answer = 18; correct answer = 18;

Test #15:

score: 12
Accepted
time: 29ms
memory: 161416kb

input:

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

output:

14 28
6 1 2 9 10 3 4 5 7 8 
4 8 10 1 9 7 6 2 5 3

result:

points 1.0 correct answer = 14; correct answer = 28;

Test #16:

score: 12
Accepted
time: 19ms
memory: 162560kb

input:

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

output:

16 22
6 4 10 5 7 8 9 1 3 2 
4 10 8 1 7 9 5 3 6 2

result:

points 1.0 correct answer = 16; correct answer = 22;

Test #17:

score: 12
Accepted
time: 20ms
memory: 163908kb

input:

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

output:

12 34
8 7 4 10 9 2 6 1 5 3 
8 4 5 2 3 9 10 1 6 7

result:

points 1.0 correct answer = 12; correct answer = 34;

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #18:

score: 38
Accepted
time: 20ms
memory: 161388kb

input:

256
229 81
255 131
55 23
79 6
37 152
3 58
173 242
17 131
116 72
109 201
92 187
215 83
101 253
224 23
101 157
219 236
214 61
41 78
190 232
184 215
39 145
215 94
21 255
59 178
255 215
25 63
46 41
77 203
164 206
28 147
195 134
204 155
215 256
107 167
202 95
206 69
57 222
87 25
52 63
69 234
73 110
54 34...

output:

316 2186
131 44 58 97 209 130 24 249 230 179 89 214 106 74 182 255 237 63 207 35 175 68 55 7 87 75 70 147 100 159 83 150 98 54 20 112 152 48 145 43 78 154 136 2 125 180 123 79 233 221 222 18 213 34 224 71 51 3 178 169 129 95 52 173 4 81 229 22 84 27 56 116 200 14 165 23 203 46 38 39 251 66 31 168 18...

result:

points 1.0 correct answer = 316; correct answer = 2186;

Test #19:

score: 38
Accepted
time: 41ms
memory: 161956kb

input:

500
223 499
155 198
156 203
423 438
87 11
3 73
394 298
59 42
394 147
499 377
50 44
144 298
131 147
10 38
235 430
463 288
103 165
339 354
467 76
414 450
50 206
129 443
147 409
476 409
445 239
111 398
293 273
349 296
131 149
206 92
454 183
313 209
390 480
155 406
494 75
408 382
10 100
166 102
123 332
...

output:

636 5114
186 331 73 415 410 399 474 187 321 51 109 491 477 4 228 482 29 23 15 87 466 16 253 211 34 341 188 163 233 425 498 329 336 447 487 442 153 10 481 44 134 154 164 40 159 368 264 127 490 279 38 184 378 106 437 492 303 48 22 473 226 273 192 28 262 340 349 428 414 395 429 110 3 307 25 205 267 391...

result:

points 1.0 correct answer = 636; correct answer = 5114;

Test #20:

score: 38
Accepted
time: 23ms
memory: 164588kb

input:

499
239 23
393 140
346 79
261 477
343 157
9 31
466 9
459 488
365 191
38 405
302 340
413 434
227 499
40 318
289 373
290 394
21 479
287 322
52 378
422 283
86 369
39 444
19 321
132 302
31 364
301 142
417 6
25 219
199 223
405 372
133 67
89 449
412 39
382 418
21 379
244 391
477 469
246 484
423 416
6 9
36...

output:

614 4106
23 121 215 242 68 436 386 312 466 120 356 324 51 149 495 357 143 10 321 427 479 296 239 282 477 492 481 417 165 319 364 216 434 35 164 115 409 332 444 318 185 236 29 73 225 270 424 275 159 307 13 378 352 248 430 8 119 314 469 438 12 217 145 453 175 350 133 308 287 299 118 435 473 276 410 29...

result:

points 1.0 correct answer = 614; correct answer = 4106;

Test #21:

score: 38
Accepted
time: 20ms
memory: 164100kb

input:

1000
842 343
479 865
720 325
420 693
317 105
694 123
626 422
306 24
186 483
37 830
103 33
328 345
379 819
79 946
835 433
939 455
271 587
980 524
316 643
204 621
573 60
935 924
984 435
880 123
626 3
689 794
110 378
827 351
487 932
201 193
836 706
874 293
889 845
179 815
800 267
43 934
954 916
805 548...

output:

1294 14376
255 599 95 408 257 846 941 792 725 703 741 972 391 547 940 239 392 756 541 731 238 891 299 306 121 608 931 9 818 717 457 605 103 274 621 949 830 691 961 742 979 933 310 263 357 797 494 905 169 745 234 874 982 303 912 718 288 716 748 988 122 591 368 667 28 623 157 854 23 269 61 261 795 409...

result:

points 1.0 correct answer = 1294; correct answer = 14376;

Test #22:

score: 38
Accepted
time: 28ms
memory: 163976kb

input:

999
731 687
673 842
221 812
673 902
239 774
18 251
133 461
396 647
376 819
966 519
30 617
297 574
275 88
926 172
907 465
774 303
10 404
547 728
352 357
549 413
27 309
297 843
573 49
556 523
289 655
769 549
16 581
402 576
411 75
981 413
12 108
850 434
627 353
263 752
165 746
761 856
88 375
312 90
761...

output:

1244 11674
810 616 295 861 537 475 187 491 464 404 308 45 931 681 652 581 49 937 835 212 839 963 73 560 359 129 166 26 105 617 831 860 987 67 326 81 591 112 347 385 678 503 59 465 650 282 715 99 17 535 189 653 568 448 171 598 525 748 530 367 722 490 646 343 397 587 277 840 236 637 113 145 898 792 19...

result:

points 1.0 correct answer = 1244; correct answer = 11674;

Test #23:

score: 38
Accepted
time: 38ms
memory: 161472kb

input:

987
840 63
459 542
449 461
397 392
585 630
322 108
449 806
10 433
529 449
702 617
674 975
417 156
983 5
746 66
208 232
244 402
162 331
695 175
616 42
528 765
437 100
425 26
96 133
37 91
93 690
317 201
189 128
576 566
847 64
65 684
217 445
214 217
151 369
4 527
91 763
978 87
739 6
802 70
417 786
199 ...

output:

1266 11812
918 668 729 527 514 739 865 785 609 717 309 790 518 920 401 248 241 707 427 303 271 933 371 93 372 780 378 457 885 393 48 910 575 110 190 852 91 363 208 764 562 387 636 695 721 675 447 31 365 366 743 420 540 334 54 344 191 864 467 312 619 900 840 907 684 746 698 593 415 314 551 408 660 80...

result:

points 1.0 correct answer = 1266; correct answer = 11812;

Test #24:

score: 38
Accepted
time: 20ms
memory: 161772kb

input:

1000
618 292
281 35
663 995
702 117
25 252
913 959
740 974
985 395
23 397
352 905
932 681
209 542
745 500
346 371
449 506
856 812
664 545
999 23
813 227
554 944
455 541
472 53
224 39
91 484
139 731
620 233
759 253
279 151
857 450
353 400
797 482
63 43
81 516
141 943
382 660
977 45
240 589
267 47
560...

output:

1000 500000
902 350 486 860 69 680 799 576 730 482 842 850 604 615 654 376 721 763 736 64 635 873 999 555 252 195 73 510 464 737 502 272 397 740 281 420 99 798 752 220 196 558 63 198 977 934 267 245 126 832 452 590 472 302 529 720 65 969 505 657 714 864 43 20 57 207 578 153 5 425 219 710 27 375 349 ...

result:

points 1.0 correct answer = 1000; correct answer = 500000;

Test #25:

score: 38
Accepted
time: 28ms
memory: 161816kb

input:

999
871 760
692 751
234 935
861 721
846 760
231 625
667 861
258 596
771 61
876 782
69 799
567 422
927 920
318 235
58 911
26 383
257 606
228 738
476 428
381 292
46 988
144 814
277 532
770 648
217 32
405 941
130 603
146 661
58 503
912 714
377 256
92 637
477 395
88 278
438 294
708 356
906 149
381 140
9...

output:

1140 91036
729 711 453 310 147 12 120 207 115 750 648 6 247 36 355 840 114 618 287 650 419 949 89 122 31 836 53 464 733 510 25 217 880 712 713 14 110 673 564 49 628 709 717 326 255 119 686 455 40 700 937 789 27 68 366 747 866 911 285 676 771 282 304 748 788 636 702 309 753 2 663 425 801 265 154 174 ...

result:

points 1.0 correct answer = 1140; correct answer = 91036;

Test #26:

score: 38
Accepted
time: 23ms
memory: 161744kb

input:

909
140 106
583 520
460 181
523 659
107 351
900 122
135 31
368 867
262 110
128 579
640 445
14 818
378 341
196 117
350 400
62 348
879 597
318 618
283 37
315 523
239 879
207 458
905 574
35 127
479 883
812 550
342 590
410 624
462 782
422 560
858 526
8 125
215 447
182 360
17 369
803 7
372 219
8 455
1 64...

output:

1028 43956
64 732 571 357 22 754 803 474 507 21 237 404 23 405 894 547 369 477 99 810 10 39 13 213 552 899 117 819 111 792 847 391 469 558 716 291 875 242 5 639 155 65 533 130 565 255 864 779 172 78 87 176 90 719 371 904 723 842 109 586 244 348 679 1 42 292 752 817 742 68 897 688 695 245 485 856 542...

result:

points 1.0 correct answer = 1028; correct answer = 43956;

Test #27:

score: 38
Accepted
time: 19ms
memory: 161780kb

input:

1000
322 537
402 605
63 899
250 892
64 985
806 42
40 618
948 945
686 85
348 536
451 664
612 443
474 780
352 690
778 812
308 289
958 516
389 284
672 366
556 944
569 496
43 364
484 570
738 954
766 402
935 933
696 214
925 559
889 858
590 219
1000 473
609 580
418 357
271 466
758 929
682 878
678 778
917 ...

output:

1002 250998
407 494 686 447 924 434 742 709 673 456 414 160 780 488 858 30 790 552 214 972 599 663 508 946 642 351 973 448 585 16 423 564 671 813 699 374 674 574 679 728 812 806 364 958 710 566 388 939 947 967 286 694 138 834 320 724 820 375 201 178 983 166 123 637 963 587 586 862 518 228 669 936 93...

result:

points 1.0 correct answer = 1002; correct answer = 250998;

Test #28:

score: 38
Accepted
time: 32ms
memory: 164156kb

input:

1000
944 65
357 755
504 31
900 759
916 234
547 41
761 831
282 858
855 983
770 797
539 473
492 455
18 323
915 294
690 69
935 463
701 665
259 215
102 55
5 876
375 735
810 578
371 785
687 757
213 649
307 658
988 462
610 810
870 847
521 97
637 589
173 702
492 426
16 872
412 705
667 778
592 943
810 872
1...

output:

1248 127496
521 650 219 129 600 128 507 427 836 147 344 919 511 112 624 21 980 323 756 563 872 612 107 145 609 608 996 676 182 834 965 377 983 333 773 958 720 699 833 790 221 725 236 979 628 206 297 273 84 467 74 812 227 411 134 466 636 10 522 499 691 366 215 590 299 170 937 39 690 220 454 633 245 3...

result:

points 1.0 correct answer = 1248; correct answer = 127496;

Test #29:

score: 38
Accepted
time: 27ms
memory: 161496kb

input:

1000
275 786
275 833
193 275
948 275
409 275
275 988
539 275
275 267
187 275
367 275
556 275
425 275
295 275
275 763
587 275
73 275
40 275
275 709
912 275
64 275
847 275
275 979
275 520
239 275
701 275
477 275
275 454
356 275
906 275
420 275
814 275
739 275
30 275
275 95
502 275
550 275
275 230
275 ...

output:

1998 1998
552 957 682 387 403 330 186 145 899 987 676 157 686 473 632 941 60 959 845 759 315 291 947 1 650 809 689 885 214 95 55 136 225 278 872 348 661 220 43 709 662 478 170 735 240 456 395 699 613 211 321 944 755 867 449 882 744 612 175 758 910 242 408 847 270 811 203 250 869 955 659 746 40 447 5...

result:

points 1.0 correct answer = 1998; correct answer = 1998;

Test #30:

score: 38
Accepted
time: 27ms
memory: 161480kb

input:

989
740 463
740 19
531 322
740 544
177 531
531 147
937 531
740 365
876 740
750 740
67 531
881 740
740 838
765 740
740 304
344 740
22 531
740 176
491 531
772 740
531 187
833 740
531 933
372 740
740 840
740 295
740 685
740 769
452 531
740 471
740 766
740 846
531 971
740 590
740 212
720 740
721 740
166...

output:

1974 2962
408 36 116 675 167 413 516 411 852 473 635 805 625 109 803 74 442 35 544 874 81 491 75 506 227 474 141 727 11 228 499 371 25 743 584 293 511 348 651 637 171 249 245 257 4 659 338 9 753 321 577 203 863 677 160 657 705 68 858 415 145 595 725 222 185 783 22 855 78 97 50 96 886 702 6 488 883 2...

result:

points 1.0 correct answer = 1974; correct answer = 2962;

Test #31:

score: 38
Accepted
time: 27ms
memory: 163888kb

input:

1000
215 913
18 659
755 775
60 282
156 687
282 591
797 850
448 282
577 484
637 282
345 913
85 289
634 695
775 746
475 362
489 190
894 269
913 696
831 21
92 547
913 795
267 579
982 839
547 571
21 219
547 759
770 298
258 364
85 878
298 279
85 81
643 504
775 643
18 524
775 952
263 770
775 611
587 775
2...

output:

1940 7958
907 997 33 109 574 120 899 889 195 282 803 423 605 87 603 51 314 659 302 142 831 633 259 108 275 52 405 303 669 914 826 564 7 373 485 676 293 821 23 377 214 122 441 189 157 490 662 141 756 843 666 238 233 187 96 209 643 445 393 591 528 647 678 597 558 248 291 950 757 151 739 935 69 646 607...

result:

points 1.0 correct answer = 1940; correct answer = 7958;

Test #32:

score: 38
Accepted
time: 12ms
memory: 161456kb

input:

888
310 287
55 464
55 160
2 713
73 237
427 193
2 61
679 55
45 73
117 73
73 432
55 785
797 861
704 55
312 861
397 73
474 317
73 43
434 474
213 861
566 801
861 301
230 73
737 2
134 566
427 337
480 55
11 73
577 861
427 114
674 474
887 185
429 427
861 723
316 474
861 819
206 732
73 346
568 55
887 20
2 8...

output:

1756 4288
344 713 707 696 466 529 5 569 678 27 346 141 396 147 96 745 512 36 476 144 164 876 375 533 419 219 355 814 221 727 431 519 866 254 665 782 192 110 759 390 778 503 230 252 117 560 886 340 495 402 772 531 86 689 464 885 693 762 271 190 737 265 35 289 328 486 418 25 202 406 881 347 237 44 294...

result:

points 1.0 correct answer = 1756; correct answer = 4288;

Test #33:

score: 38
Accepted
time: 24ms
memory: 161748kb

input:

1000
60 327
715 322
13 49
48 263
3 523
770 46
551 160
751 160
580 859
392 466
560 282
461 86
339 127
644 539
530 202
605 852
511 550
563 309
425 92
22 17
708 583
134 156
449 225
274 300
578 569
579 335
729 539
464 579
510 79
77 497
593 497
614 636
555 942
8 13
920 67
957 412
613 632
906 649
579 399
...

output:

1392 9628
746 701 523 226 856 669 975 242 996 664 416 985 49 767 451 653 670 433 71 272 208 17 994 823 278 945 881 615 941 695 671 719 918 870 314 525 816 588 134 340 67 385 713 393 940 770 837 595 894 789 726 293 302 33 909 802 70 716 155 434 205 532 247 993 986 874 920 338 790 310 292 300 351 818 ...

result:

points 1.0 correct answer = 1392; correct answer = 9628;

Test #34:

score: 38
Accepted
time: 24ms
memory: 163700kb

input:

987
543 539
482 744
58 699
322 99
741 808
107 99
248 230
247 917
934 869
438 424
248 258
393 578
632 704
786 418
683 882
679 730
849 46
203 968
33 972
155 223
799 154
154 291
527 867
424 739
731 323
424 484
158 86
452 679
799 686
138 818
672 600
424 853
424 247
331 261
734 772
754 780
15 103
482 552...

output:

1782 6554
193 758 766 717 30 815 678 803 983 335 472 870 729 185 957 10 871 771 187 964 503 235 907 689 431 380 147 691 163 583 707 642 972 790 593 63 612 601 535 664 392 728 125 348 319 219 475 845 921 308 177 59 331 617 526 522 985 699 374 580 916 451 16 385 877 785 913 675 796 131 209 946 669 462...

result:

points 1.0 correct answer = 1782; correct answer = 6554;

Test #35:

score: 38
Accepted
time: 20ms
memory: 164548kb

input:

975
645 307
416 645
377 175
639 842
527 377
591 444
134 7
42 569
305 194
598 758
7 209
850 175
598 975
471 393
303 444
614 320
126 598
671 194
444 564
728 444
338 598
324 947
733 891
906 515
124 752
175 470
752 243
727 645
547 455
670 499
687 444
590 444
662 552
7 175
444 39
349 444
597 444
473 639
...

output:

1874 5278
682 876 537 723 857 926 134 588 41 153 435 104 667 256 465 372 313 915 676 619 959 804 274 751 841 339 151 875 660 707 284 326 352 831 218 290 581 169 349 962 457 569 142 910 694 645 920 388 361 439 392 324 526 320 67 97 900 419 199 466 70 483 26 579 922 341 484 132 923 774 609 210 442 927...

result:

points 1.0 correct answer = 1874; correct answer = 5278;

Test #36:

score: 38
Accepted
time: 12ms
memory: 161432kb

input:

1000
538 932
941 662
61 662
90 217
276 538
721 260
75 979
217 53
235 684
769 662
538 497
662 355
414 662
147 217
235 309
44 235
217 689
156 217
498 235
52 217
217 617
709 662
662 510
306 662
583 752
578 662
721 258
662 603
217 249
286 235
734 75
662 165
291 721
721 482
917 110
340 235
538 800
217 42...

output:

1980 3906
470 850 171 46 231 351 113 456 947 996 328 911 823 531 398 69 768 751 238 128 785 25 690 841 710 523 50 528 907 63 846 336 640 501 240 611 118 575 738 307 649 592 701 498 713 94 59 579 561 633 199 617 147 628 990 58 594 786 536 21 769 359 362 298 412 820 394 867 916 440 476 644 215 647 979...

result:

points 1.0 correct answer = 1980; correct answer = 3906;

Test #37:

score: 38
Accepted
time: 28ms
memory: 164252kb

input:

1000
620 802
417 303
67 87
300 180
67 880
7 453
826 481
720 505
67 754
841 823
67 35
592 402
940 481
599 438
5 67
681 353
890 399
438 732
542 667
258 399
502 667
583 530
399 391
479 949
210 742
337 681
232 512
417 996
417 170
417 97
870 567
470 620
4 849
186 870
559 348
702 288
374 417
681 362
67 99...

output:

1890 6546
510 390 240 849 994 712 453 770 763 201 251 518 535 638 947 233 198 950 758 853 432 134 395 833 911 501 92 422 403 168 22 78 262 684 5 204 389 640 613 755 818 884 225 618 493 866 89 177 979 221 683 16 623 414 29 462 137 576 999 943 815 163 220 123 918 469 87 926 821 699 521 685 735 203 189...

result:

points 1.0 correct answer = 1890; correct answer = 6546;

Test #38:

score: 38
Accepted
time: 27ms
memory: 161492kb

input:

1000
520 185
785 97
15 774
521 437
421 163
906 123
869 429
520 538
459 70
97 943
178 39
475 97
742 637
705 417
502 520
57 705
487 123
627 97
469 59
403 123
165 437
123 264
369 538
231 57
786 715
96 15
762 794
437 744
692 893
794 437
135 437
794 74
765 9
305 57
924 15
57 965
469 559
520 163
690 449
1...

output:

1938 4626
222 30 263 667 899 630 512 399 765 806 997 719 752 506 774 169 932 791 496 367 112 356 685 119 535 319 767 99 82 738 646 102 962 756 313 737 761 989 152 816 406 89 759 255 996 888 723 477 787 139 784 987 333 986 493 272 231 539 559 188 913 788 705 852 802 840 296 365 438 459 77 458 978 844...

result:

points 1.0 correct answer = 1938; correct answer = 4626;

Test #39:

score: 38
Accepted
time: 15ms
memory: 161516kb

input:

999
683 443
89 76
60 664
625 39
3 811
337 527
687 154
956 443
695 664
702 100
290 957
20 445
154 397
260 823
347 154
620 299
339 664
154 851
170 620
397 781
68 154
155 264
823 555
281 445
620 697
397 213
815 75
811 896
953 397
290 997
154 13
677 664
9 823
527 166
544 154
989 445
11 39
75 570
535 39
...

output:

1938 4914
186 886 896 460 363 573 410 906 292 744 535 541 544 953 124 647 536 518 425 281 607 644 374 93 132 835 382 244 558 770 929 385 175 805 614 704 191 77 625 115 786 379 101 501 190 912 522 737 839 913 597 17 435 378 439 571 183 105 464 695 910 452 529 678 925 92 767 13 673 497 578 394 766 655...

result:

points 1.0 correct answer = 1938; correct answer = 4914;

Test #40:

score: 38
Accepted
time: 32ms
memory: 163988kb

input:

900
825 630
478 117
271 20
293 597
588 280
290 348
412 433
387 597
269 638
841 101
395 379
30 742
836 550
447 438
714 478
535 872
816 386
124 378
358 519
407 843
628 82
875 108
282 500
690 811
465 475
490 629
786 654
287 238
381 686
821 193
299 425
252 626
164 471
195 293
159 408
315 443
166 843
293...

output:

1066 7882
737 171 788 353 587 509 218 409 153 335 344 103 648 503 305 376 364 649 858 271 704 405 538 774 349 373 415 740 346 70 520 529 849 65 677 635 549 666 53 697 887 745 235 359 591 184 293 545 809 513 896 263 39 539 417 734 150 327 818 167 496 610 669 495 34 892 253 200 483 31 442 484 374 873 ...

result:

points 1.0 correct answer = 1066; correct answer = 7882;

Test #41:

score: 0
Wrong Answer
time: 19ms
memory: 161468kb

input:

888
235 292
649 771
880 641
57 46
480 401
401 762
587 856
432 475
428 95
698 807
294 713
179 818
166 730
118 714
722 764
745 484
258 474
597 394
822 301
306 202
774 847
643 886
663 772
235 78
734 243
171 718
173 357
539 681
816 186
225 335
702 427
662 626
810 886
258 865
95 722
258 38
764 307
880 60...

output:

445586 10654
19 769 366 272 51 547 388 473 424 27 227 258 648 67 868 225 231 292 525 764 597 164 327 10 242 430 142 558 78 593 620 130 117 421 311 888 678 806 382 94 649 74 205 466 521 57 680 636 107 665 805 887 808 393 463 737 54 809 834 686 879 245 147 510 420 831 14 559 585 16 733 264 501 42 316 ...

result:

wrong answer Integer parameter [name=vi] equals to 0, violates the range [1, 888]

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

Server Time: 2024-12-02 15:36:03 | OpenSource Project