QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207738#6638. Treelectionyx20220802WA 36ms5076kbC++141.9kb2023-10-08 19:41:362023-10-08 19:41:37

Judging History

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

  • [2023-10-08 19:41:37]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:5076kb
  • [2023-10-08 19:41:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace IO_ER{
    #define LL long long
    #define db double
    #define U unsigned
    #define ULL U LL
    #define In inline
    #define Re register
    #define f(a,b,i) for(int i=a;i<=b;i++)
    #define ff(a,b,i) for(int i=a;i<b;i++)
    #define f_(a,b,i) for(int i=a;i>=b;i--)
    #define ff_(a,b,i) for(int i=a;i>b;i--)
    typedef pair<LL,int> Pi;
    int inf=0x3f3f3f3f;
    int INF=0x7fffffff;
    LL infll=0x3f3f3f3f3f3f3f3fll;
    LL INFll=0x7fffffffffffffffll;
    template<typename T>void read(T &x){
        x=0;
        int fl=0;
        char ch=getchar();
        while(ch<'0'||'9'<ch){
            if(ch=='-')fl=1;
            ch=getchar();
        }
        while('0'<=ch&&ch<='9'){
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        x=fl?-x:x;
    }
    template<typename T,typename ...Args>void read(T &x,Args &...args){
        read(x);
        read(args...);
    }
}
using namespace IO_ER;

#define N 100050

int n;

int fa[N];

int sz[N];

int dp[N];

In bool pd(int x){
    f(1,n,i)dp[i]=0;
    f_(n,2,i){
		dp[i]=max(dp[i]-x,0);
        dp[fa[i]]+=dp[i]+1;
    }
    return dp[1]<=x;
}

int tag[N];

int main(){
    int Ti;
    read(Ti);
    while(Ti--){
        read(n);
        f(2,n,i)read(fa[i]);
        f(1,n,i)tag[i]=sz[i]=0;
        f_(n,2,i)sz[fa[i]]+=sz[i]+1;
        int l=1,r=n;
        int ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(pd(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        pd(ans-1);
        if(dp[1]==ans){
            tag[1]=1;
            f(2,n,i)tag[i]=(tag[fa[i]]&&dp[i]);
        }
        f(1,n,i){
            if(sz[i]>ans||(sz[i]==ans&&tag[i]))putchar('1');
            else putchar('0');
        }
        puts("");
    }
    return 0;
}

詳細信息

Test #1:

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

input:

2
4
1 2 3
5
1 1 2 2

output:

1100
10000

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 36ms
memory: 4976kb

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:

ok 10 lines

Test #3:

score: -100
Wrong Answer
time: 7ms
memory: 5076kb

input:

1
1000000
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...1111111111111111111111111111100'