QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #121769 | #2596. Even Forest | BZJRN | WA | 1ms | 7728kb | C++14 | 1.2kb | 2023-07-08 20:16:53 | 2023-07-08 20:16:54 |
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("%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]);
}
/*
5
1 2
2 3
3 4
1 5
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: 7724kb
input:
4 1 2 2 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7728kb
input:
4 1 2 1 3 1 4
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 7704kb
input:
6 1 2 2 3 4 2 4 5 6 4
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'