QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#718178	#9607. 熟练	Nesraychan	100 ✓	484ms	147728kb	C++14	2.9kb	2024-11-06 19:53:38	2024-11-06 19:53:39

Judging History

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

[2024-11-06 19:53:39]
评测

测评结果：100
用时：484ms
内存：147728kb

查看

[2024-11-06 19:53:38]
提交

answer

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 500500
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

int testcnt,testid;
int n,m,a[N],b[N];
std::vector<int>G[N],vec[N];

IL void add(reg int u,reg int v){G[u].push_back(v),G[v].push_back(u);}

int sz[N],son[N],fa[N],dep[N];

void dfs1(reg int u)
{
    sz[u]=1,dep[u]=dep[fa[u]]+1,son[u]=0;
    for(auto v:G[u])if(!sz[v])
    {
        fa[v]=u,dfs1(v),sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    }
}

int anc[N],dfn[N],ed[N],p[N],dfc;

void dfs2(reg int u,reg int rt)
{
    anc[u]=rt,p[dfn[u]=++dfc]=u;
    if(son[u])dfs2(son[u],rt);
    for(auto v:G[u])if(!anc[v])dfs2(v,v);
    ed[u]=dfc;
}

IL int lca(reg int x,reg int y)
{
    for(;anc[x]!=anc[y];x=fa[anc[x]])
        if(dep[anc[x]]<dep[anc[y]])std::swap(x,y);
    return dep[x]<dep[y]?x:y;
}

int ans[N],f[N];

IL void cmax(reg int &x,reg int y){x<y?x=y:0;}

int s[N];
std::vector<int>ad[N],dl[N],S;
bool in[N];
int pos;

IL void ins(reg int x)
{
    ++s[x];
    if(s[x]&&!in[x])in[x]=1,S.push_back(x);
}

IL void del(reg int x)
{
    --s[x];
}

IL int query()
{
    while(!s[S.back()])in[S.back()]=0,S.pop_back();
    return S.back();
}

IL void flood(reg int l,reg int r,reg int k)
{
    if(l<=pos)del(k); else ad[l].push_back(k);
    if(r<pos)ins(k); else dl[r].push_back(k);
}

IL void flood_tree(reg int x,reg int y,reg int k)
{
    while(anc[x]!=anc[y])
    {
        if(dep[anc[x]]<dep[anc[y]])std::swap(x,y);
        flood(dfn[anc[x]],dfn[x],k),x=fa[anc[x]];
    }
    if(dep[x]<dep[y])flood(dfn[x],dfn[y],k);
    else flood(dfn[y],dfn[x],k);
}

void dfs3(reg int u)
{
    for(auto v:G[u])if(v!=fa[u])
        dfs3(v),f[u]+=f[v];
}

IL void work()
{
    n=read(),m=read();
    for(reg int i=1;i<=n;++i)G[i].clear(),vec[i].clear(),anc[i]=sz[i]=f[i]=0;
    for(reg int i=1;i<=n;++i)ad[i].clear(),dl[i].clear();
    for(reg int i=1;i<n;++i)add(read(),read());
    for(reg int i=1;i<=m;++i)a[i]=read(),b[i]=read();
    dfs1(1),dfc=0,dfs2(1,1);
    for(reg int i=1,c;i<=m;++i)
    {
        c=lca(a[i],b[i]);
        ++f[a[i]],++f[b[i]],--f[c],--f[fa[c]];
        vec[c].push_back(i);
    }
    dfs3(1); reg int mx=0;
    for(reg int i=1;i<=n;++i)cmax(mx,f[i]);
    printf("%d\n",mx),S.clear();
    for(reg int i=1;i<=mx;++i)s[i]=in[i]=0;
    for(reg int i=1;i<=mx;++i)ins(i);
    for(reg int i=1,u;i<=n;++i)
    {
        for(auto x:ad[i])del(x);
        u=p[i],pos=i;
        for(auto x:vec[u])
            flood_tree(a[x],b[x],ans[x]=query());
        for(auto x:dl[i])ins(x);
    }
    for(reg int i=1;i<=m;++i)printf("%d%c",ans[i]," \n"[i==m]);
}

main()
{
    testid=read(),testcnt=read();
    while(testcnt--)work();
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 54ms

memory: 71364kb

input:

output:

result:

ok ok

Subtask #2:

score: 14

Accepted

Dependency #1:

100%

Accepted

Test #2:

score: 14

Accepted

time: 51ms

memory: 90828kb

input:

output:

result:

ok ok

Test #3:

score: 14

Accepted

time: 122ms

memory: 104932kb

input:

output:

result:

ok ok

Test #4:

score: 14

Accepted

time: 61ms

memory: 82852kb

input:

output:

result:

ok ok

Test #5:

score: 14

Accepted

time: 72ms

memory: 83584kb

input:

output:

result:

ok ok

Test #6:

score: 14

Accepted

time: 34ms

memory: 71332kb

input:

output:

result:

ok ok

Test #7:

score: 14

Accepted

time: 38ms

memory: 74208kb

input:

output:

result:

ok ok

Test #8:

score: 14

Accepted

time: 75ms

memory: 84592kb

input:

output:

result:

ok ok

Test #9:

score: 14

Accepted

time: 103ms

memory: 80768kb

input:

output:

result:

ok ok

Test #10:

score: 14

Accepted

time: 150ms

memory: 90768kb

input:

output:

result:

ok ok

Subtask #3:

score: 9

Accepted

Test #11:

score: 9

Accepted

time: 201ms

memory: 144640kb

input:

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

output:

66
46 18 55 18 41 27 16 43 39 51 54 45 28 23 19 26 29 47 52 23 8 65 43 48 5 14 44 38 9 40 4 29 11 23 57 58 53 21 52 60 29 36 27 31 32 37 16 57 31 35 50 13 20 60 64 17 63 60 56 38 65 63 27 42 9 37 49 44 52 34 18 61 30 28 41 23 25 15 40 27 30 56 24 33 47 4 22 54 15 53 2 58 59 62 25 61 6 66 59 53 12 46...

result:

ok ok

Test #12:

score: 9

Accepted

time: 117ms

memory: 92436kb

input:

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

output:

12758
10983 3193 5 7934 5048 6413 10752 10597 11337 7660 4441 2005 2224 3662 4670 4106 12533 8438 5950 6137 2652 6911 11974 6029 475 11625 1283 4509 11891 3675 3704 210 5854 10636 908 9233 12450 557 7064 1769 2913 11999 6469 2703 313 8536 3709 8749 6445 9435 5699 487 1040 190 4072 5479 1536 3566 4 7...

result:

ok ok

Test #13:

score: 9

Accepted

time: 101ms

memory: 71300kb

input:

output:

160
90 111 57 132 154 131 136 77 21 127 35 114 150 119 61 60 27 145 47 44 67 120 7 28 2 107 73 37 100 135 88 70 56 105 29 93 91 16 157 12 151 137 97 90 43 83 45 80 66 69 81 44 97 147 16 109 17 11 115 72 64 81 133 70 124 144 108 99 98 100 48 114 151 151 152 50 150 104 86 79 15 148 10 125 31 68 126 13...

result:

ok ok

Test #14:

score: 9

Accepted

time: 98ms

memory: 74248kb

input:

output:

558
411 383 133 342 433 149 423 49 183 184 377 368 325 267 386 475 200 410 173 354 488 264 553 228 319 363 293 98 263 54 164 558 490 21 240 290 33 171 245 117 457 275 209 112 107 392 206 230 469 208 446 249 253 34 313 167 103 311 113 375 526 469 454 464 434 349 85 449 476 421 462 151 94 554 199 550 ...

result:

ok ok

Test #15:

score: 9

Accepted

time: 218ms

memory: 147728kb

input:

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

output:

28970
1919 17248 10376 24718 9038 11645 10000 5028 4288 26002 5948 19411 3080 26846 21150 12244 20237 23158 15747 12058 3765 13623 9570 12183 25434 7102 16949 12722 523 14545 17918 2848 13050 26548 10862 4850 9291 6206 28777 7561 17021 23345 6199 16612 23050 10205 28878 13104 27649 4599 8853 4772 20...

result:

ok ok

Test #16:

score: 9

Accepted

time: 226ms

memory: 142344kb

input:

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

output:

183
112 36 86 170 56 88 45 149 146 69 12 48 161 164 96 170 175 161 116 24 38 164 15 118 109 73 160 73 94 46 41 95 104 121 151 44 133 84 74 111 77 138 81 29 80 102 123 107 89 79 60 120 83 97 148 165 57 111 72 140 131 12 166 172 85 123 119 180 177 59 118 105 182 63 7 179 178 51 20 134 135 170 127 79 1...

result:

ok ok

Subtask #4:

score: 20

Accepted

Test #17:

score: 20

Accepted

time: 11ms

memory: 70904kb

input:

output:

839
527 839 838 23 837 836 835 834 833 832 23 831 830 829 828 827 826 825 824 823 822 527 821 820 87 819 818 817 816 87 815 814 813 812 301 811 43 810 87 809 808 807 806 805 804 803 802 527 801 800 799 798 797 796 795 794 793 45 792 791 790 789 788 787 786 785 23 784 783 389 782 781 780 779 778 777 ...

result:

ok ok

Test #18:

score: 20

Accepted

time: 4ms

memory: 70784kb

input:

output:

417
265 56 185 21 85 349 302 369 328 92 356 153 135 83 363 221 384 358 194 246 112 369 264 15 301 413 309 245 94 410 160 382 220 408 251 100 208 51 219 396 353 205 82 166 405 240 401 45 166 177 358 28 384 176 373 310 272 400 198 138 214 390 66 321 305 387 152 138 366 45 66 280 414 417 20 368 60 244 ...

result:

ok ok

Test #19:

score: 20

Accepted

time: 4ms

memory: 71756kb

input:

output:

161
161 160 159 135 127 158 19 24 19 9 59 72 71 96 138 97 157 13 127 129 122 44 79 36 97 64 148 150 151 95 151 130 113 3 63 36 87 152 72 31 158 155 138 20 88 37 90 115 120 43 6 76 161 157 143 19 118 91 78 159 142 57 37 39 159 82 12 113 11 35 17 48 13 16 16 149 10 90 153 154 55 156 90 150 100 18 104 ...

result:

ok ok

Test #20:

score: 20

Accepted

time: 7ms

memory: 70700kb

input:

output:

473
204 347 452 233 3 405 220 418 304 198 186 452 233 202 37 181 167 121 55 284 316 301 397 202 92 187 407 137 436 123 140 127 199 274 99 439 339 359 411 434 91 148 265 398 357 309 123 420 329 159 138 276 351 150 157 329 278 449 72 343 262 224 392 248 378 111 159 237 264 282 224 66 52 157 73 133 263...

result:

ok ok

Test #21:

score: 20

Accepted

time: 3ms

memory: 73932kb

input:

output:

196
59 196 60 73 195 92 194 193 192 191 151 51 190 169 55 7 19 189 188 54 53 187 7 186 52 185 184 4 183 51 50 182 47 181 180 179 178 177 6 176 175 5 174 4 49 173 48 172 47 171 170 169 46 188 168 6 167 166 45 44 165 59 164 43 11 163 162 161 160 4 42 41 4 159 158 59 157 156 155 154 153 152 151 150 149...

result:

ok ok

Test #22:

score: 20

Accepted

time: 3ms

memory: 71784kb

input:

output:

216
216 94 215 23 95 214 152 3 100 102 17 213 103 212 211 210 105 209 208 207 206 205 204 203 96 107 113 108 173 202 97 106 98 109 112 201 20 20 193 200 199 70 49 113 46 4 198 49 116 118 197 80 196 170 59 195 82 99 194 55 193 192 191 190 65 189 93 188 170 95 92 187 186 185 184 183 182 181 180 179 17...

result:

ok ok

Test #23:

score: 20

Accepted

time: 3ms

memory: 70312kb

input:

output:

175
30 117 76 93 6 104 168 62 130 161 80 119 74 165 107 69 120 95 46 123 77 71 40 57 91 133 36 32 135 5 153 41 52 110 111 60 68 112 31 111 37 3 32 116 22 12 91 123 42 72 73 50 108 16 135 99 89 98 88 54 44 113 101 148 160 162 146 31 73 25 65 84 170 143 32 164 100 147 129 131 54 159 101 103 19 78 150 ...

result:

ok ok

Test #24:

score: 20

Accepted

time: 3ms

memory: 71164kb

input:

output:

588
500 8 3 6 122 18 588 587 586 10 585 584 583 121 582 3 581 562 112 580 579 9 578 577 576 575 59 574 573 368 120 572 119 118 571 570 117 116 569 568 513 293 184 567 566 565 564 116 124 563 562 561 560 559 558 557 115 556 114 131 125 113 555 112 111 554 27 455 553 110 552 551 550 109 549 548 547 54...

result:

ok ok

Test #25:

score: 20

Accepted

time: 4ms

memory: 71024kb

input:

output:

123
9 123 26 121 122 13 120 10 70 12 10 2 11 119 12 48 11 12 81 118 8 123 3 120 13 119 13 122 14 121 117 14 4 5 120 116 15 14 121 15 9 15 118 10 115 114 16 6 119 16 113 17 7 11 13 70 117 14 17 15 12 118 116 18 16 115 117 17 16 19 112 17 20 18 18 19 19 120 114 20 21 18 19 111 110 113 22 109 108 20 21...

result:

ok ok

Test #26:

score: 20

Accepted

time: 7ms

memory: 70396kb

input:

output:

648
648 42 647 646 645 644 73 394 154 643 642 641 38 640 78 639 638 28 637 80 636 635 634 633 9 85 503 632 631 630 17 629 628 12 277 627 626 15 625 624 623 622 621 620 619 618 617 616 615 614 34 613 14 308 612 611 11 610 89 609 13 8 608 607 606 26 605 604 92 603 20 93 602 22 309 24 601 600 19 599 59...

result:

ok ok

Test #27:

score: 20

Accepted

time: 9ms

memory: 70944kb

input:

output:

675
18 72 257 265 588 587 272 274 281 301 586 283 22 306 60 350 206 367 385 585 584 148 583 582 30 161 35 675 581 580 579 428 578 432 577 576 575 436 461 574 38 472 496 573 572 513 177 571 570 514 569 568 567 523 527 40 97 529 540 566 573 47 565 564 563 562 561 50 674 137 560 574 673 672 559 575 558...

result:

ok ok

Test #28:

score: 20

Accepted

time: 4ms

memory: 71048kb

input:

output:

377
143 145 377 183 76 376 375 151 374 2 152 154 373 3 64 162 8 372 371 370 369 157 368 367 366 155 365 165 364 166 153 363 156 362 361 360 359 173 9 358 170 357 356 355 354 353 352 192 351 184 171 188 11 248 26 350 349 348 280 299 32 347 322 327 13 346 145 345 337 342 184 365 344 135 134 133 40 343...

result:

ok ok

Test #29:

score: 20

Accepted

time: 12ms

memory: 72020kb

input:

output:

261
2 261 260 259 258 257 256 255 254 253 61 252 251 250 249 248 247 246 245 244 243 242 241 3 240 239 27 238 41 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 10 81 207 206 205 204 203 40 202 201 200 199 198 197 196 195 8 194 ...

result:

ok ok

Test #30:

score: 20

Accepted

time: 3ms

memory: 70320kb

input:

output:

34
32 13 8 23 19 26 10 34 10 18 29 26 2 5 17 27 5 17 17 8 30 11 23 11 15 18 5 21 12 18 16 24 17 9 20 30 10 22 19 12 19 11 14 18 9 34 19 21 25 12 11 26 30 15 12 24 33 18 23 30 7 31 31 20 4 27 32 16 23 26 4 14 12 24 31 20 32 18 28 6 30 15 20 23 20 11 24 17 3 12 14 18 15 5 32 12 31 9 32 34 18 18 7 7 33...

result:

ok ok

Test #31:

score: 20

Accepted

time: 7ms

memory: 72120kb

input:

output:

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

result:

ok ok

Test #32:

score: 20

Accepted

time: 13ms

memory: 70944kb

input:

output:

150
117 150 47 149 2 148 89 147 3 4 64 32 146 86 5 145 85 144 116 5 93 70 6 38 109 7 143 8 142 29 141 9 147 71 140 72 36 89 139 68 41 12 10 115 138 18 93 146 31 89 11 92 30 35 14 19 91 31 91 20 17 3 142 2 56 69 35 137 77 12 22 51 33 114 24 25 141 93 13 32 26 14 136 135 32 92 15 52 18 94 80 84 84 17 ...

result:

ok ok

Subtask #5:

score: 22

Accepted

Dependency #4:

100%

Accepted

Test #33:

score: 22

Accepted

time: 76ms

memory: 80808kb

input:

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

output:

27238
27238 27237 27236 27235 26630 11057 27234 6269 27233 27232 27231 27230 27229 27228 27227 27226 27225 27224 27223 24520 27222 27221 27220 27219 27218 27217 27216 27215 27214 27213 27212 27211 27210 27209 27208 27207 27206 27205 27204 27203 27202 27201 27200 10237 27199 27198 13398 27197 27196 2...

result:

ok ok

Test #34:

score: 22

Accepted

time: 83ms

memory: 85432kb

input:

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

output:

43611
40691 43611 43610 43609 16778 16784 43608 16786 43607 28473 16801 16805 43606 16806 2 33666 16808 16814 16815 43605 16819 36380 43604 25664 16823 40307 43603 16825 12465 16833 16836 43602 24687 43601 16842 25024 16843 23936 43600 16850 43599 3 16862 16864 1735 41738 43598 43597 16866 4 43596 1...

result:

ok ok

Test #35:

score: 22

Accepted

time: 87ms

memory: 88540kb

input:

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

output:

58693
58693 910 58692 58691 2361 18837 665 50207 58690 58689 18836 58688 58687 58686 18835 18834 58685 58684 58683 3 58682 16822 17829 6 18833 58681 58680 58679 5419 18832 58678 58677 58676 58675 58674 57740 37737 58673 20736 18839 18831 18830 18829 58672 58671 58670 28732 58669 18828 58668 4783 188...

result:

ok ok

Test #36:

score: 22

Accepted

time: 38ms

memory: 75956kb

input:

output:

11000
11000 10999 10998 10997 6510 10996 10995 4494 10994 10993 10992 10991 10990 10989 2288 10988 10987 2653 10986 1736 10985 10984 10983 10982 10981 10980 10979 10978 10977 10976 10975 4731 10974 10973 2666 10972 10971 10970 10969 2492 10968 10967 10966 10965 10964 10963 10962 10961 10960 10959 10...

result:

ok ok

Test #37:

score: 22

Accepted

time: 33ms

memory: 75036kb

input:

output:

3386
3386 3385 955 3384 3383 3382 3381 956 3380 3379 957 958 959 960 1414 3378 3377 2 3376 961 3375 962 3374 3373 249 963 3 3372 964 3371 3370 3369 332 965 3368 966 967 3367 3366 3365 968 1330 3364 3363 3362 3361 4 969 3360 3359 3358 5 3357 3356 970 971 3355 3354 3353 972 174 351 3352 3351 3350 3349...

result:

ok ok

Test #38:

score: 22

Accepted

time: 34ms

memory: 76904kb

input:

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

output:

1051
258 549 123 240 1051 497 576 1050 1049 578 629 652 241 1048 242 672 677 678 684 124 1047 125 692 699 581 706 126 708 1046 786 243 712 1045 715 723 1044 736 743 1043 127 402 1042 789 128 1041 244 794 1040 245 246 1039 838 1038 551 756 967 146 28 178 178 247 626 129 128 151 130 440 717 248 480 32...

result:

ok ok

Test #39:

score: 22

Accepted

time: 35ms

memory: 73008kb

input:

output:

451
451 268 2 450 347 3 277 295 4 449 318 5 321 6 329 448 7 357 8 344 9 447 10 362 11 446 12 445 13 14 364 15 367 369 385 444 16 17 401 18 19 20 21 22 414 23 24 25 443 416 26 437 442 447 361 27 28 368 261 29 260 396 441 398 440 352 259 30 31 32 33 439 438 437 436 435 34 35 366 36 37 434 433 38 258 2...

result:

ok ok

Test #40:

score: 22

Accepted

time: 25ms

memory: 73084kb

input:

output:

118
53 118 117 116 118 115 114 113 112 111 110 2 109 108 107 106 105 104 103 60 110 102 59 101 100 99 98 97 96 95 94 93 3 92 91 90 89 88 87 86 85 84 83 82 4 103 81 52 55 60 2 51 5 6 80 72 79 56 58 78 3 61 96 71 57 56 7 77 70 8 90 69 50 76 88 111 9 75 54 68 67 2 6 3 91 74 61 55 49 48 61 117 53 66 7 6...

result:

ok ok

Test #41:

score: 22

Accepted

time: 23ms

memory: 72108kb

input:

output:

345
23 182 178 178 176 30 320 258 230 238 139 71 105 75 7 32 216 187 223 224 74 73 218 6 291 77 164 206 80 112 143 237 41 328 203 294 116 213 284 210 48 62 219 198 174 192 121 7 323 302 130 311 143 259 265 123 216 295 262 340 289 258 165 53 147 57 212 240 272 238 150 172 304 21 117 194 38 175 152 33...

result:

ok ok

Test #42:

score: 22

Accepted

time: 23ms

memory: 72996kb

input:

output:

695
695 614 694 693 398 528 88 438 694 104 692 124 418 487 691 222 174 690 73 689 537 375 217 185 175 311 171 180 651 621 663 538 688 466 311 514 242 170 651 59 687 229 169 686 626 646 685 242 546 684 179 66 46 168 687 167 166 689 674 683 141 5 693 548 165 668 682 179 375 207 525 164 163 431 186 83 ...

result:

ok ok

Test #43:

score: 22

Accepted

time: 61ms

memory: 83464kb

input:

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

output:

48829
34923 47337 29755 33449 46384 32759 14378 205 38007 23328 21449 41514 34521 7559 4246 35117 20155 4797 21772 39335 22063 26116 20364 28087 42997 24373 39936 43587 28252 43957 29357 41805 40549 35298 30808 28607 24913 30809 2449 28806 13360 13032 23527 6704 2234 1417 10093 3330 19990 43471 3473...

result:

ok ok

Test #44:

score: 22

Accepted

time: 63ms

memory: 80184kb

input:

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

output:

126
20 40 126 125 124 123 122 110 121 120 119 118 2 117 116 115 57 114 113 112 26 21 111 110 109 42 40 108 107 106 105 104 37 103 102 101 100 99 120 98 97 96 21 95 94 93 92 120 4 91 90 5 89 115 88 87 22 86 85 84 83 82 81 26 80 79 78 77 76 54 75 74 71 8 35 73 72 71 70 69 42 68 67 66 65 64 63 62 10 4 ...

result:

ok ok

Test #45:

score: 22

Accepted

time: 51ms

memory: 84012kb

input:

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

output:

10182
287 10182 10181 288 10180 10179 10178 10177 10176 289 186 290 291 230 7840 173 239 8253 174 253 231 249 175 250 7640 232 176 251 10175 292 293 252 221 222 253 177 233 234 10174 235 223 187 10179 10173 10172 10171 254 294 255 236 188 295 224 189 289 225 290 10170 256 296 237 291 257 190 258 191...

result:

ok ok

Test #46:

score: 22

Accepted

time: 47ms

memory: 83440kb

input:

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

output:

31782
5555 30851 23936 15041 15139 31531 3598 20743 19556 26190 21919 12445 29960 5621 9522 16847 26625 29460 22805 3306 12056 25303 14427 4877 15445 11550 10311 13328 2083 31156 9875 9612 13849 18103 16666 19234 30318 17189 12199 20118 26678 20742 27056 19972 19744 25283 17937 29763 23881 30452 590...

result:

ok ok

Test #47:

score: 22

Accepted

time: 28ms

memory: 75260kb

input:

output:

4114
4114 4113 4112 4111 4110 4109 4108 2 4107 4106 4105 4104 4103 3 4102 4101 4100 4 4099 4098 4097 3233 4096 4095 4094 4093 4092 4091 4090 1273 3060 4089 627 4088 4087 4086 4085 3057 4084 4083 4082 4081 772 4080 2944 284 4079 4078 3053 1226 4077 4076 775 4075 4074 5 6 4073 4072 4071 4070 4069 2934...

result:

ok ok

Test #48:

score: 22

Accepted

time: 34ms

memory: 75344kb

input:

output:

2862
2102 1264 1412 2063 2507 664 2443 1987 1613 1603 503 1977 2010 2172 83 1220 2426 569 2057 1768 2433 900 2325 2791 2673 633 549 1467 2158 1480 2030 122 2015 534 2064 2707 2815 30 1642 2425 1186 1278 1429 136 1825 912 741 1012 2726 1668 395 669 563 2806 2796 343 1934 1008 2479 1167 599 813 172 80...

result:

ok ok

Subtask #6:

score: 32

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Test #49:

score: 32

Accepted

time: 207ms

memory: 146724kb

input:

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

output:

120
15 46 48 7 117 19 58 53 70 61 91 103 94 10 67 76 39 23 40 51 30 28 102 93 58 29 59 19 29 107 59 96 102 92 44 83 116 46 104 67 113 71 51 30 64 111 66 30 110 57 112 38 69 71 61 43 8 72 87 109 86 4 88 112 34 99 22 87 44 48 78 111 36 60 46 56 78 62 117 102 113 59 83 9 115 95 101 36 90 50 39 84 70 24...

result:

ok ok

Test #50:

score: 32

Accepted

time: 247ms

memory: 142632kb

input:

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

output:

232572
201217 74545 121309 60239 186598 67768 49600 2750 190435 85836 195318 228110 16092 162524 200448 197861 173047 85256 228239 84187 127214 52361 102025 192369 202471 186460 147704 47885 173111 57415 108455 139344 173644 104281 200178 143475 46513 205149 146722 182407 225473 219527 175232 123091...

result:

ok ok

Test #51:

score: 32

Accepted

time: 484ms

memory: 124904kb

input:

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

output:

347915
347915 347914 347913 347912 347911 347910 347909 147774 347908 347907 347906 347905 347904 347903 347902 347901 347900 347899 347898 347897 347896 347895 347894 347893 347892 347891 347890 74280 347889 347888 347887 347886 347885 347884 347883 336358 347882 92843 347881 347880 347879 347878 3...

result:

ok ok

Test #52:

score: 32

Accepted

time: 277ms

memory: 106616kb

input:

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

output:

80099
2 49101 80099 80098 49107 49113 49117 80097 49119 19982 80096 49120 49122 49127 80095 8857 49130 12980 49132 3 80094 80093 80092 49135 80091 49142 4 80090 49147 49152 5 49156 49157 49158 49161 14484 49162 49163 80089 1228 80088 49166 6 80087 49176 49178 49179 20558 80086 49181 34722 51207 4918...

result:

ok ok

Test #53:

score: 32

Accepted

time: 255ms

memory: 111120kb

input:

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

output:

8376
8376 8375 8374 464 5590 162 8153 3969 6253 7939 6325 3674 2119 2086 8373 201 5948 661 813 4414 334 4140 879 7219 4060 5013 7965 3904 8372 6482 2239 7141 730 6999 3436 2363 4613 8371 7133 6406 8370 8369 5763 5041 8368 4795 6891 2668 456 6586 2940 214 2785 8367 253 6488 5734 4028 274 7095 3086 23...

result:

ok ok

Test #54:

score: 32

Accepted

time: 174ms

memory: 98348kb

input:

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

output:

62086
48411 5853 26359 52704 23543 44663 40250 7202 15184 54932 33325 49353 40879 55661 21207 34345 41143 54639 35761 57113 35424 36826 41138 27710 30210 46590 23595 7597 14847 54813 12775 34497 42917 20542 20817 55952 14936 16773 20160 3095 58921 60921 8148 26732 21601 36851 55834 25997 22731 53422...

result:

ok ok

Test #55:

score: 32

Accepted

time: 122ms

memory: 73364kb

input:

output:

604
604 603 127 602 82 450 599 351 303 276 600 21 122 601 107 598 107 222 153 121 120 597 596 91 595 464 594 182 593 127 592 591 590 417 589 300 588 562 282 301 365 587 25 593 394 88 586 166 404 147 211 485 450 149 272 440 260 26 585 584 495 119 583 118 23 208 154 300 582 581 580 579 251 578 269 577...

result:

ok ok

Test #56:

score: 32

Accepted

time: 121ms

memory: 74856kb

input:

output:

1521
1521 1520 1519 10 1518 1517 1516 429 3 1515 1514 103 1131 1513 428 1512 1511 1510 1509 1353 892 427 1508 426 1507 7 425 220 1353 196 193 1506 1505 1504 1344 87 34 624 1503 1502 379 1501 1500 95 1499 1498 22 1497 87 1496 430 424 1495 423 1494 1493 8 1492 205 17 1491 1490 1489 432 67 478 1488 422...

result:

ok ok

Test #57:

score: 32

Accepted

time: 112ms

memory: 73724kb

input:

output:

747
152 747 746 160 745 744 743 79 128 13 159 158 76 157 19 742 741 740 156 162 739 395 155 738 154 146 737 736 735 153 734 110 733 732 152 152 618 151 731 730 729 728 727 162 164 726 20 251 725 26 724 723 26 165 50 93 542 722 150 165 721 557 720 719 149 569 555 718 96 717 716 715 542 148 714 713 16...

result:

ok ok

Test #58:

score: 32

Accepted

time: 118ms

memory: 76772kb

input:

output:

344
2 69 344 343 342 341 70 340 71 339 72 338 337 336 73 335 3 334 333 332 331 330 74 144 75 329 328 327 326 76 4 325 324 77 78 323 79 322 321 80 81 320 82 83 319 318 317 84 316 85 315 314 313 312 311 310 309 86 87 308 307 88 306 305 304 89 147 90 91 92 93 5 303 302 301 94 95 96 97 300 98 99 330 6 2...

result:

ok ok

Test #59:

score: 32

Accepted

time: 117ms

memory: 75272kb

input:

output:

730
730 729 441 57 728 727 726 725 724 723 33 217 400 722 109 721 720 171 52 719 222 718 5 382 30 407 203 717 716 396 715 205 372 407 371 266 434 98 714 713 606 56 712 711 710 109 87 432 709 17 423 708 18 707 616 158 441 243 100 241 420 121 386 34 279 366 253 706 705 12 372 201 704 703 188 2 55 702 ...

result:

ok ok

Test #60:

score: 32

Accepted

time: 264ms

memory: 143088kb

input:

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

output:

204856
113431 45643 121269 28666 85047 43231 63490 199661 189730 99806 165404 80314 135596 69823 32243 98068 162183 169579 152955 182996 8051 120525 73268 35092 23503 140590 115899 99374 174857 17406 112491 136844 180560 86571 56437 174501 58026 118866 23687 110006 30367 127315 95847 203868 111109 6...

result:

ok ok