QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#121760#2596. Even ForestBZJRNWA 1ms7572kbC++141.1kb2023-07-08 19:54:592023-07-08 19:55:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-08 19:55:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7572kb
  • [2023-07-08 19:54:59]
  • 提交

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]=f[y]+1<dp[y][0]?f[y]+1:dp[y][0];
			dp[x][1]=f[y]+1<dp[y][1]?f[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]<dp[x][0]?dp[x][1]:dp[x][0];
//	printf("dp[%d,0]=%d\tdp[%d,1]=%d\tf[%d]=%d\n",x,dp[x][0],x,dp[x][1],x,f[x]);
}
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",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]);
}
/*
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
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7572kb

input:

4
1 2
2 3
3 4

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 7572kb

input:

4
1 2
1 3
1 4

output:

1

result:

wrong answer 1st numbers differ - expected: '0', found: '1'