QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207217 | #6638. Treelection | lefy | WA | 3ms | 11436kb | C++14 | 1020b | 2023-10-08 11:28:18 | 2023-10-08 11:28:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int fa[N],sz[N],full[N],dp[N],n;
int check(int mid){
for(int i=1;i<=n;i++)dp[i]=0;
for(int i=n;i>1;i--){
dp[i]=max(0,dp[i]-mid);
dp[fa[i]]+=dp[i]+1;
}
// if(mid==1)cout<<dp[1]<<"*\n";
return dp[1]<=mid;
}
void solve(){
scanf("%d",&n);
for(int i=2;i<=n;i++)scanf("%d",&fa[i]);
for(int i=n;i>=1;i--){
sz[i]++;
if(fa[i])sz[fa[i]]+=sz[i];
}
int l=1,r=n,w;
while(l<=r){
int mid=l+r>>1;
if(check(mid))w=mid,r=mid-1;
else l=mid+1;
}
// cout<<w<<"\n";
check(w-1);memset(full,0,sizeof(full));
full[1]=1;
if(dp[1]==w){
for(int i=2;i<=n;i++){
if(dp[i]&&full[fa[i]])full[i]=1;
}
}
for(int i=1;i<=n;i++)if(sz[i]-1>w||sz[i]-1==w&&full[i])printf("1");else printf("0");
printf("\n");
}
int main() {
int T;
scanf("%d",&T);
while(T--)solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 11436kb
input:
2 4 1 2 3 5 1 1 2 2
output:
1100 11000
result:
wrong answer 2nd lines differ - expected: '10000', found: '11000'