QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#176845#5455. TreeScriptlzqy_#TL 664ms8580kbC++14928b2023-09-12 07:53:402023-09-12 07:53:40

Judging History

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

  • [2023-09-12 07:53:40]
  • 评测
  • 测评结果：TL
  • 用时：664ms
  • 内存：8580kb
查看
  • [2023-09-12 07:53:40]
  • 提交

answer

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int maxn=200010;
il int read(){
	int x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
struct edge{
	int v,to;
}e[maxn<<1];
int head[maxn],ecnt;
void addedge(int u,int v){
	e[++ecnt].v=v,e[ecnt].to=head[u],head[u]=ecnt;
}
int T,n,f[maxn];
void dfs(int fa,int x){
	int Mx=0,cMx=0;
	for(int i=head[x];i;i=e[i].to)
		if(e[i].v^fa){
			dfs(x,e[i].v);
			if(f[e[i].v]>Mx) cMx=Mx,Mx=f[e[i].v];
			else if(f[e[i].v]>cMx) cMx=f[e[i].v];
		}
	f[x]=max(Mx,cMx+1);
}
void clear(){
	for(int i=1;i<=ecnt;i++) head[e[i].v]=0;
	for(int i=1;i<=n;i++) f[i]=0;
}
int main(){
	T=read();
	while(T--){
		clear();
		n=read();
		for(int i=1;i<=n;i++){
			int x=read();
			if(x) addedge(x,i),addedge(i,x);
		}dfs(0,1),printf("%d\n",f[1]);
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 86ms
memory: 6904kb

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:

4
4
3
4
3
4
5
5
4
4
4
4
5
5
3
4
4
5
3
5
5
3
5
4
5
4
5
3
4
5
2
5
4
3
5
5
4
3
3
4
4
4
3
3
4
4
5
5
4
4
4
2
4
5
5
4
4
5
4
4
5
4
3
4
4
4
4
4
5
4
4
5
5
4
5
5
2
3
4
1
1
5
5
4
3
4
5
5
4
5
4
4
4
4
4
4
4
4
4
4
5
4
4
6
5
5
3
3
5
3
4
3
3
3
4
4
3
2
4
4
3
5
3
5
3
4
4
4
5
4
5
4
5
4
4
3
5
4
4
3
3
3
3
2
5
5
4
2
4
5
...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 11ms
memory: 8580kb

input:

1
200000
0 1 2 1 4 2 3 4 1 7 9 3 4 13 9 15 11 7 7 14 5 11 16 1 5 21 11 11 6 4 23 27 22 32 24 35 28 3 8 31 18 4 32 38 39 23 37 37 13 1 35 30 20 3 39 36 46 6 14 20 37 3 2 23 56 43 34 10 58 49 67 49 9 69 48 65 37 12 8 6 47 44 36 7 50 15 29 12 53 26 66 47 43 64 29 69 41 13 1 20 52 21 51 100 33 79 58 76 ...

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 9ms
memory: 7716kb

input:

10
14713
0 1 2 2 1 5 1 4 3 4 7 10 3 3 12 15 5 5 9 15 18 15 2 9 8 14 1 17 28 26 27 28 7 11 23 20 29 29 1 30 17 31 38 17 34 42 28 13 23 27 16 14 5 19 40 37 28 36 31 16 54 26 5 5 63 29 16 38 10 16 17 33 50 29 12 21 62 53 42 52 22 57 58 81 76 67 72 43 28 16 90 64 88 75 49 92 84 47 8 5 75 57 7 11 88 57 7...

output:

7
8
7
7
8
8
8
8
7
9

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 664ms
memory: 7760kb

input:

10000
9
0 1 1 2 3 1 1 1 8
3
0 1 2
3
0 1 1
34
0 1 1 3 4 5 5 3 1 5 7 9 9 8 14 8 2 4 11 4 19 19 15 19 18 1 12 6 11 25 11 1 15 7
11
0 1 2 3 3 1 1 6 7 7 1
2
0 1
44
0 1 1 3 4 1 5 5 7 7 2 11 9 1 2 1 10 10 4 3 11 7 5 7 16 15 13 16 27 5 9 17 15 16 19 28 33 31 11 3 34 18 24 22
18
0 1 2 2 2 5 5 2 5 3 9 8 7 13 ...

output:

2
1
2
3
3
1
4
3
3
3
2
3
2
2
2
2
3
2
3
2
2
2
3
3
3
2
3
3
2
2
3
3
3
2
2
1
3
2
2
3
3
2
2
2
2
2
3
4
2
1
2
2
3
3
3
1
3
3
2
4
2
2
3
4
4
2
2
2
3
2
4
3
2
2
2
3
3
2
3
3
2
2
3
3
3
2
4
2
3
3
2
2
3
3
2
3
2
2
1
3
3
2
3
4
3
2
3
3
3
2
3
2
3
3
4
2
3
1
3
2
3
2
2
2
2
3
3
2
3
3
2
3
1
3
3
3
3
3
2
3
2
2
2
3
3
3
2
3
2
3
...

result:

ok 10000 numbers

Test #6:

score: -100
Time Limit Exceeded

input:

20000
2
0 1
14
0 1 1 1 1 1 2 2 4 1 7 8 5 9
11
0 1 2 3 2 3 1 3 8 9 3
6
0 1 1 3 3 4
16
0 1 2 2 2 5 1 4 8 4 3 3 7 9 1 15
2
0 1
3
0 1 1
21
0 1 1 2 2 5 5 3 5 4 2 5 5 6 11 11 1 12 1 6 20
3
0 1 2
5
0 1 1 2 1
27
0 1 1 1 4 2 6 7 6 2 3 1 6 1 11 3 9 12 17 11 13 17 12 6 4 17 11
7
0 1 1 2 3 4 1
4
0 1 1 2
3
0 1 2...

output:

1
2
2
2
3
1
2
3
1
2
3
2
2
1
2
1
3
3
2
2
2
3
1
2
2
2
2
3
2
3
3
2
3
2
4
3
2
1
2
3
2
2
2
3
1
3
3
2
3
2
2
2
2
2
2
1
3
2
3
2
2
2
1
3
2
1
2
3
3
3
2
2
2
2
2
3
3
3
3
1
2
2
2
2
2
1
2
2
2
2
3
3
3
1
2
3
1
2
3
2
1
3
3
2
2
2
2
3
2
2
2
2
1
1
2
1
2
2
2
2
3
2
2
2
1
1
1
2
2
2
1
2
2
2
3
2
2
2
3
2
2
1
3
2
1
2
2
2
2
1
...

result:
English 繁體中文 简体中文

Server Time: 2024-12-02 15:55:48 | OpenSource Project