QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #121780 | #2596. Even Forest | BZJRN | WA | 222ms | 36704kb | C++14 | 1.2kb | 2023-07-08 20:38:54 | 2023-07-08 20:38:54 |
Judging History
answer
#include<stdio.h>
int n,u,v,i=1,e[2000003],d[1000002],f[1000002],hd[1000002],nxt[2000003],dp[1000002][2];
void df(int x,int fa){
int y,p=hd[x];
for(f[x]=1-f[fa],dp[x][!f[x]]=!nxt[hd[x]];p;p=nxt[p]){
if(e[p]-fa){
y=e[p],df(y,x);
dp[x][0]+=d[y]+1<dp[y][0]?d[y]+1:dp[y][0];
dp[x][1]+=d[y]+1<dp[y][1]?d[y]+1:dp[y][1];
}
// dp[x][f[x]]=f[y]+1<dp[y][f[x]]?f[y]+1:dp[y][f[x]];
// dp[x][!f[x]]=f[y]+1<dp[y][!f[x]]?f[y]+1:dp[y][!f[x]];
}
d[x]=nxt[nxt[hd[x]]]&&dp[x][1-f[x]]<dp[x][f[x]]?dp[x][1-f[x]]:dp[x][f[x]];
// printf("f[%d]=%d\td[%d]=%d\tdp[%d,0]=%d\tdp[%d,1]=%d\n",x,f[x],x,d[x],x,dp[x][0],x,dp[x][1]);
}
int main(){
for(scanf("%d",&n);i<n*2-1;++i)scanf("%d%d",&u,&v),e[i]=v,nxt[i]=hd[u],hd[u]=i,++i,e[i]=u,nxt[i]=hd[v],hd[v]=i;
df(1,0),printf("%d",d[1]);
// df(1,0),printf("\n%d",nxt[hd[1]]&&dp[1][1-f[1]]<dp[1][f[1]]?dp[1][1-f[1]]:dp[1][f[1]]);
// for(i=1;i<=n;++i)printf("\ndp[%d][0]=%d dp[%d][1]=%d",i,dp[i][0],i,dp[i][1]);
// for(i=1;i<=n;++i,puts(""))for(printf("%d:",i),p=hd[i];p;p=nxt[p])printf("%d ",e[p]);
}
/*
3
1 2
1 3
4
1 2
2 3
3 4
7
1 2
1 3
2 4
4 5
4 6
3 7
1
|
4
/|\
2 5 3
|
6
/ \
7 8
4
/\
1 5
/\ \
2 3 6
\
7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7580kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7740kb
input:
4 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7692kb
input:
6 1 2 2 3 4 2 4 5 6 4
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7568kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 7716kb
input:
3 2 3 3 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 7740kb
input:
4 2 3 3 1 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 7576kb
input:
5 4 2 2 3 4 1 5 3
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 1ms
memory: 7700kb
input:
6 4 3 1 4 2 4 5 2 4 6
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
50 21 22 22 27 22 7 22 12 22 13 43 22 36 22 35 22 6 22 10 22 22 38 19 22 34 22 8 22 22 44 22 3 9 22 22 16 23 22 18 22 22 25 22 5 22 2 22 15 46 22 37 22 48 22 33 22 22 17 31 22 22 29 22 28 22 49 4 22 22 26 41 22 22 32 22 50 22 20 22 30 24 22 40 22 22 45 14 22 22 11 42 22 39 22 1 22 47 22
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 174ms
memory: 36688kb
input:
1000000 851841 325834 455962 325834 135775 325834 525341 325834 265267 325834 868520 325834 834325 325834 867971 325834 325834 879726 325834 242607 325834 106951 122113 325834 325834 499633 727580 325834 325834 200171 325834 178877 325834 493841 957118 325834 325834 809324 325834 641895 325834 33338...
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 0ms
memory: 7692kb
input:
3 2 1 2 3
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 1ms
memory: 7720kb
input:
4 4 3 1 4 1 2
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 1ms
memory: 7740kb
input:
5 1 4 2 4 3 2 3 5
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 1ms
memory: 7560kb
input:
6 3 5 3 6 1 6 1 4 4 2
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 1ms
memory: 7740kb
input:
7 1 2 3 2 6 3 6 7 7 4 4 5
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 1ms
memory: 7744kb
input:
8 6 2 1 2 8 1 5 8 5 7 7 3 4 3
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 0ms
memory: 7740kb
input:
20 6 1 6 15 9 15 18 9 18 17 17 7 8 7 3 8 19 3 2 19 13 2 13 11 12 11 12 14 4 14 4 5 20 5 16 20 16 10
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 7572kb
input:
42 33 30 17 33 17 7 29 7 15 29 15 23 23 1 10 1 10 31 4 31 12 4 12 34 28 34 28 41 41 11 32 11 32 24 13 24 13 19 26 19 16 26 35 16 35 27 37 27 37 3 3 20 8 20 39 8 6 39 6 42 14 42 14 38 38 9 25 9 18 25 18 5 36 5 36 40 40 21 21 2 22 2
output:
1
result:
ok 1 number(s): "1"
Test #20:
score: 0
Accepted
time: 1ms
memory: 7736kb
input:
27 19 14 6 19 16 19 19 7 19 4 21 19 26 4 26 15 4 5 5 1 10 26 13 26 17 7 3 4 23 13 21 25 2 25 2 12 10 9 20 17 24 16 21 27 22 13 8 16 18 7 11 24
output:
6
result:
ok 1 number(s): "6"
Test #21:
score: 0
Accepted
time: 0ms
memory: 7760kb
input:
2007 1852 380 380 1300 1437 380 380 1789 380 876 380 1427 1295 1852 380 1549 782 1549 205 380 1789 446 1300 1113 380 417 446 1357 1295 242 446 1758 579 417 562 242 1086 1437 1584 876 579 1981 1873 1789 1918 1789 376 1437 1113 1564 30 1113 1357 1197 221 446 1300 128 386 579 1918 1126 479 1549 1026 15...
output:
326
result:
ok 1 number(s): "326"
Test #22:
score: 0
Accepted
time: 1ms
memory: 7716kb
input:
582 422 513 284 422 571 422 148 422 422 315 420 422 422 143 92 422 422 94 177 422 67 422 112 422 422 424 343 422 219 422 422 263 422 131 19 422 422 322 422 257 455 422 371 422 422 580 431 422 422 160 123 422 531 422 422 474 422 189 471 422 422 168 77 422 438 422 232 422 422 336 239 422 422 467 186 4...
output:
65
result:
ok 1 number(s): "65"
Test #23:
score: 0
Accepted
time: 0ms
memory: 7748kb
input:
2007 1191 1713 1191 1921 1191 63 1191 272 1191 774 1191 1116 656 1191 1191 154 1872 1191 453 1191 1191 411 1599 1191 1420 1191 810 1191 1191 1470 1191 1017 457 1191 1191 987 101 1191 1794 1191 1191 1404 134 1191 1080 1191 918 1191 955 1191 1191 1124 1191 1042 1191 1369 1191 51 88 1191 1315 1191 1191...
output:
7
result:
ok 1 number(s): "7"
Test #24:
score: 0
Accepted
time: 1ms
memory: 7680kb
input:
50 43 40 28 43 32 43 50 43 29 43 43 45 43 49 43 2 43 5 43 23 7 43 43 31 43 35 43 38 4 43 16 43 43 8 20 43 20 33 43 13 39 13 9 43 17 9 18 43 18 37 43 42 42 25 43 14 41 14 43 10 27 10 3 43 48 3 43 26 19 26 43 47 24 47 21 43 6 21 11 43 11 34 43 30 22 30 43 44 46 44 43 1 1 12 43 36 36 15
output:
16
result:
ok 1 number(s): "16"
Test #25:
score: 0
Accepted
time: 0ms
memory: 7584kb
input:
505 4 447 447 441 120 447 238 447 447 108 447 256 38 447 447 464 77 447 292 447 447 276 130 447 237 447 478 447 100 447 414 447 245 447 447 195 295 447 349 447 447 119 173 447 203 447 501 447 192 447 447 421 447 223 447 282 470 447 447 174 128 447 447 422 236 447 104 447 91 447 447 16 447 270 447 42...
output:
168
result:
ok 1 number(s): "168"
Test #26:
score: 0
Accepted
time: 1ms
memory: 7804kb
input:
5500 4460 4560 4560 144 254 4560 4560 1154 1101 4560 4560 5187 729 4560 4560 298 4560 22 4441 4560 1706 4560 2584 4560 4560 3066 2773 4560 4560 2333 4560 3361 3821 4560 5438 4560 467 4560 908 4560 1682 4560 4560 1340 4560 3916 4560 2230 5190 4560 4560 3998 4560 1318 4560 1834 2237 4560 1263 4560 504...
output:
1833
result:
ok 1 number(s): "1833"
Test #27:
score: 0
Accepted
time: 5ms
memory: 10228kb
input:
50555 36789 49023 43923 36789 36789 13246 36789 48699 2773 36789 39874 36789 36789 16692 36789 17216 44101 36789 10095 36789 36789 10290 36789 50112 40378 36789 31137 36789 36789 8862 36789 16420 49359 36789 11341 36789 36789 19825 36789 23690 36789 38450 3972 36789 36789 43666 39461 36789 14201 367...
output:
16851
result:
ok 1 number(s): "16851"
Test #28:
score: 0
Accepted
time: 89ms
memory: 27704kb
input:
505000 381245 387591 381245 193068 246759 381245 381245 408770 113785 381245 377328 381245 394893 381245 381245 425648 448511 381245 381245 305387 381245 193354 499135 381245 381245 181417 305596 381245 381245 204529 381245 380041 488911 381245 76718 381245 381245 248514 381245 452149 381245 425516 ...
output:
168333
result:
ok 1 number(s): "168333"
Test #29:
score: 0
Accepted
time: 165ms
memory: 36644kb
input:
1000000 986875 629957 986875 931053 986875 77814 986875 116863 986875 154708 986875 121402 986875 273150 986875 368825 538061 986875 894517 986875 665786 986875 986875 240057 981735 986875 986875 154176 583988 986875 787550 986875 585571 986875 986875 655060 989566 986875 121052 986875 671384 986875...
output:
333333
result:
ok 1 number(s): "333333"
Test #30:
score: 0
Accepted
time: 166ms
memory: 36680kb
input:
1000000 227871 955120 227871 690016 227871 180027 227871 751799 268526 227871 526636 227871 970122 227871 452015 227871 227871 766778 227871 685720 227871 650207 227871 977238 581273 227871 199253 227871 227871 208659 227871 726438 70773 227871 440886 227871 227871 385013 230118 227871 792363 227871...
output:
219295
result:
ok 1 number(s): "219295"
Test #31:
score: 0
Accepted
time: 174ms
memory: 36704kb
input:
1000000 742740 400594 400594 980404 913320 400594 400594 611227 930291 400594 872935 400594 84718 400594 351806 400594 746664 400594 500676 400594 294634 400594 809371 400594 803109 400594 572897 400594 400594 668232 598480 400594 476146 400594 537662 400594 197536 400594 400594 944275 640135 400594...
output:
85598
result:
ok 1 number(s): "85598"
Test #32:
score: -100
Wrong Answer
time: 222ms
memory: 36568kb
input:
1000000 211617 660262 852360 660262 660262 45281 660262 820334 95971 660262 712556 660262 660262 243112 423933 660262 660262 246067 705132 660262 660262 589878 466992 660262 346803 660262 176058 660262 660262 120286 660262 924322 660262 284641 125075 660262 918758 660262 963266 660262 313827 660262 ...
output:
173411
result:
wrong answer 1st numbers differ - expected: '173410', found: '173411'