QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #75714 | #5455. TreeScript | chenshi# | WA | 16ms | 5692kb | C++ | 710b | 2023-02-06 08:50:37 | 2023-02-06 08:50:40 |
Judging History
answer
#include<cstdio>
#include<algorithm>
using namespace std;
const int o=2e5+10;
int T,n,p[o],h[o],cnt,f[o],g[o],st[o],tp;
struct Edge{int v,p;}e[o];
inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
inline bool cmp(int A,int B){return g[A]<g[B];}
void dfs(int nw){
for(int i=h[nw];i;i=e[i].p) dfs(e[i].v);
tp=0;
for(int i=h[nw];i;i=e[i].p) st[++tp]=e[i].v;
if(!tp){f[nw]=g[nw]=1;return;}
sort(st+1,st+tp+1,cmp);
f[nw]=min(g[nw]=g[st[tp]]+1,max(f[st[tp]],g[st[tp-1]]+1));
}
int main(){
for(scanf("%d",&T);T--;printf("%d\n",f[1]),cnt=0){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&p[i]),h[i]=0;
for(int i=2;i<=n;++i) ad(p[i],i);
dfs(1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5688kb
input:
2 3 0 1 2 7 0 1 2 2 1 4 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #2:
score: -100
Wrong Answer
time: 16ms
memory: 5692kb
input:
1000 197 0 1 1 2 1 4 1 5 8 3 5 1 4 7 12 14 4 7 10 9 12 11 16 10 21 19 22 17 25 13 28 9 5 15 26 26 33 25 15 1 35 6 32 17 37 8 19 43 19 27 29 9 30 6 31 27 35 35 37 13 28 38 57 31 38 8 22 14 33 9 18 62 52 37 10 19 22 60 54 12 38 59 64 65 80 82 28 60 85 78 27 25 71 14 52 6 59 14 87 32 33 41 59 41 88 38 ...
output:
9 11 3 8 5 7 9 10 9 8 8 8 13 10 6 6 10 11 7 10 12 5 10 10 10 9 12 6 7 12 4 11 8 5 9 9 6 6 6 7 9 7 7 4 6 8 10 10 7 8 8 4 8 8 12 8 7 10 8 8 10 11 3 9 8 7 8 9 13 8 8 10 10 8 9 11 4 6 8 1 1 11 12 7 6 6 11 11 8 10 9 9 8 7 6 7 7 6 7 9 11 10 8 11 10 10 4 7 8 6 9 6 5 4 11 9 5 3 7 9 4 9 5 12 5 8 8 6 10 6 12 ...
result:
wrong answer 1st numbers differ - expected: '4', found: '9'