QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #790851 | #5455. TreeScript | Tom22l | WA | 6ms | 6948kb | C++17 | 1.1kb | 2024-11-28 15:43:03 | 2024-11-28 15:43:03 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
int x=0;
char ch=getchar();bool f=0;
while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
int h[200005];
int nxt[200005];
int to[200005];
int cnt;
int s[200005];
int fa[200005];
void link(int x,int y){
nxt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
s[x]++;
return;
}
queue<int> q;
int ans;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T=Read();
while(T--){
int n=Read();
ans=0;
for(int i=1;i<=n;i++){
fa[i]=Read();
if(fa[i])link(fa[i],i);
else q.push(i);
}
int res=1;
while(!q.empty()){
int x=q.front();q.pop();
s[fa[x]]--;
if(!fa[x]) ans++;
else if(res) res--;
else ans++;
if(!s[fa[x]]) res++;
if(!s[x]) res++;
// cout<<x<<" is : "<<res<<' '<<ans<<endl;
for(int i=h[x];i;i=nxt[i]){
q.push(to[i]);
// printf("%d ",to[i]);
}
// printf("\n");
}
printf("%lld\n",ans);
for(int i=0;i<=n;i++) h[i]=0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5760kb
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: 6ms
memory: 6948kb
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:
23 12 3 13 8 12 32 37 8 18 12 15 59 39 7 8 32 75 10 38 66 4 21 27 27 16 67 7 13 44 3 34 10 7 36 14 5 9 7 12 17 15 8 4 11 12 42 47 10 13 15 3 9 32 51 18 20 28 12 23 37 28 4 24 22 17 8 22 41 17 10 57 49 18 22 40 3 5 23 1 1 65 37 9 9 9 32 65 14 25 22 28 18 14 8 12 11 10 16 24 26 30 15 74 24 32 3 3 33 1...
result:
wrong answer 1st numbers differ - expected: '4', found: '23'