QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#189386#6638. TreelectionqzhwlzyWA 182ms21236kbC++141.1kb2023-09-27 14:00:492023-09-27 14:00:49

Judging History

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

  • [2023-09-27 14:00:49]
  • 评测
  • 测评结果:WA
  • 用时:182ms
  • 内存:21236kb
  • [2023-09-27 14:00:49]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define maxn 1000005
using namespace std;
int T,n,x; int f[maxn],fa[maxn],siz[maxn]; bool ans[maxn]; struct node{int to,nex;}a[maxn]; int head[maxn],cnt=0;
void add(int from,int to){a[++cnt].to=to; a[cnt].nex=head[from]; head[from]=cnt;}
void getfa(int p,int fat){
	fa[p]=fat; siz[p]=1;
	for(int i=head[p];i;i=a[i].nex) if(a[i].to!=fat) getfa(a[i].to,p),siz[p]+=siz[a[i].to];
}
void check(int res,int p){
	f[p]=-res; for(int i=head[p];i;i=a[i].nex) if(a[i].to!=fa[p]) check(res,a[i].to),f[p]+=f[a[i].to];
	f[p]=max(f[p],0)+(p==1?0:1);
}
void dfs(int p){
	if(siz[p]-1>x) ans[p]=1; else if(siz[p]-1<x) ans[p]=0; else ans[p]=(f[1]==1&&f[p]==2);
	for(int i=head[p];i;i=a[i].nex) if(a[i].to!=fa[p]) dfs(a[i].to);
}
int main(){
	scanf("%d",&T); while(T--){
		scanf("%d",&n); for(int i=1;i<=n;i++) head[i]=ans[i]=f[i]=fa[i]=0; cnt=0;
		for(int i=2;i<=n;i++) scanf("%d",&x),add(x,i); getfa(1,0);
		int l=1,r=n-1,mid; x=n-1; while(l<=r){mid=(l+r)>>1; check(mid,1); if(f[1]==0) x=mid,r=mid-1; else l=mid+1;}
		check(x-1,1); dfs(1); ans[1]=1; for(int i=1;i<=n;i++) printf("%d",ans[i]); printf("\n");
	} return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 13968kb

input:

2
4
1 2 3
5
1 1 2 2

output:

1100
10000

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 182ms
memory: 21236kb

input:

10
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

wrong answer 1st lines differ - expected: '111111111111111111111111111111...0000000000000000000000000000000', found: '111111111111111111111111111111...0000000000000000000000000000000'