QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #121777 | #2596. Even Forest | BZJRN | ML | 1ms | 7728kb | C++14 | 1.2kb | 2023-07-08 20:37:38 | 2023-07-08 20:37:41 |
Judging History
answer
#include<stdio.h>
int n,u,v,i=1,e[2000003],d[1000002],f[1000002],hd[1000002],nxt[1000002],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: 0ms
memory: 7704kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7564kb
input:
4 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7700kb
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: 3540kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7724kb
input:
2 1 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 7728kb
input:
3 2 3 3 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 7640kb
input:
4 2 3 3 1 3 4
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 7696kb
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: 7716kb
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: 0ms
memory: 7708kb
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: -100
Memory Limit Exceeded
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...