QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201633#6638. Treelectionucup-team870WA 144ms43256kbC++171.3kb2023-10-05 15:40:042023-10-05 15:40:05

Judging History

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

  • [2023-10-05 15:40:05]
  • 评测
  • 测评结果:WA
  • 用时:144ms
  • 内存:43256kb
  • [2023-10-05 15:40:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
const int N=1e6+6;
int fa[N],res[N],dp[N],V,sz[N],ok[N];
vi tu[N];
void dfs(int now){
    int sum=0; sz[now]=1;
    for(int son:tu[now]){
        dfs(son); sum+=dp[son]; sz[now]+=sz[son];
    }
    dp[now]=(now!=1)+max(0,sum-V);
}
void slv(){
    int n; cin>>n;
    rep(i,1,n){
        tu[i].clear(); res[i]=0;
    }
    rep(i,2,n){
        cin>>fa[i]; tu[fa[i]].push_back(i);
    }
    int L=1,R=n-1;
    while(L<=R){
        V=L+R>>1; dfs(1);
        if(dp[1])L=V+1; 
        else R=V-1;
    }
    V=L-1; dfs(1); assert(dp[1]);
    V=L;
    ok[1]=(dp[1]==1);
    // function <void(int)> dfs0=[&](int now){
    //     for(int son:tu[now]){

    //     }
    // };
    rep(i,2,n){
        ok[i]=(dp[i] && ok[fa[i]]);
    }
    rep(i,1,n){
        int v=sz[i]-1;
        // cout<<v<<' ';
        if(v>V)res[i]=1;
        else if(v<V)res[i]=0;
        else{
            if(ok[i])res[i]=1;
            else res[i]=0;
        }
    }
    rep(i,1,n)cout<<res[i]; cout<<'\n';
}
signed main(){
    IOS
    int T;cin>>T;
    while(T--)slv();
}

详细

Test #1:

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

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: 144ms
memory: 43256kb

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'