QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207738 | #6638. Treelection | yx20220802 | WA | 36ms | 5076kb | C++14 | 1.9kb | 2023-10-08 19:41:36 | 2023-10-08 19:41:37 |
Judging History
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'