QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#418754#5124. TreeLLCS#AC ✓304ms101180kbC++17649b2024-05-23 15:35:012024-05-23 15:35:02

Judging History

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

  • [2024-05-23 15:35:02]
  • 评测
  • 测评结果：AC
  • 用时：304ms
  • 内存：101180kb
查看
  • [2024-05-23 15:35:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int nmax,d[1000010],h[1000010];
vector<int> v[1000010];
inline void dfs(int x)
{
	d[x]=1;
	for(int i=0;i<v[x].size();i++)
	{
		int u=v[x][i];
		dfs(u);
		d[x]=max(d[x],d[u]+1);
	}
}
int main()
{
	int T,n;
	scanf("%d",&T);
	while(T)
	{
		T--;nmax=0x3f3f3f3f;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) v[i].clear();
		for(int i=0;i<=n+1;++i) h[i]=d[i]=0;
		for(int i=2,x;i<=n;i++)
		{
			scanf("%d",&x);
			v[x].push_back(i);
		}
		dfs(1);
		for(int i=1;i<=n;++i){
			h[d[i]]++;
		}
		for(int i=0;i<=n;++i){
			nmax=min(nmax,i+h[i+1]);
		}
		printf("%d\n",nmax);
	}
}
源文件, 语言: C++17

詳細信息

Test #1:

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

input:

2
7
1 1 2 2 2 3
5
1 2 3 4

output:

3
1

result:

ok 2 number(s): "3 1"

Test #2:

score: 0
Accepted
time: 21ms
memory: 27292kb

input:

46234
1

2
1
3
1 1
4
1 1 1
5
1 1 1 1
6
1 1 1 1 1
7
1 1 1 1 1 1
8
1 1 1 1 1 1 1
9
1 1 1 1 1 1 1 1
9
1 1 1 1 1 1 1 2
9
1 1 1 1 1 1 1 3
9
1 1 1 1 1 1 1 4
9
1 1 1 1 1 1 1 5
9
1 1 1 1 1 1 1 6
9
1 1 1 1 1 1 1 7
9
1 1 1 1 1 1 1 8
8
1 1 1 1 1 1 2
9
1 1 1 1 1 1 2 1
9
1 1 1 1 1 1 2 2
9
1 1 1 1 1 1 2 3
9
1 1 1...

output:

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

result:

ok 46234 numbers

Test #3:

score: 0
Accepted
time: 106ms
memory: 101180kb

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:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 48ms
memory: 38764kb

input:

1
1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 169ms
memory: 66296kb

input:

1
1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1000

result:

ok 1 number(s): "1000"

Test #6:

score: 0
Accepted
time: 304ms
memory: 66416kb

input:

1
1000000
1 1 1 2 3 4 5 6 7 3 6 8 9 10 13 11 12 13 14 15 8 16 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 51 39 54 55 56 57 58 59 60 61 68 62 63 64 65 66 67 68 69 70 71 59 72 73 74 75 76 77 78 79 80 81 82 32 23 83 84 85 86 87 88 8...

output:

1405

result:

ok 1 number(s): "1405"

Test #7:

score: 0
Accepted
time: 298ms
memory: 66428kb

input:

1
1000000
1 1 1 1 2 3 4 5 6 7 8 9 10 11 14 1 12 13 14 15 19 16 17 18 19 20 21 20 22 23 24 25 26 27 28 20 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 29 46 47 48 49 50 51 52 53 54 53 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 51 76 77 78 79 80 81 82 83 84 85 86 23 87 88 89 ...

output:

1404

result:

ok 1 number(s): "1404"

Test #8:

score: 0
Accepted
time: 288ms
memory: 66360kb

input:

1
1000000
1 1 1 2 4 3 4 5 6 7 8 9 10 5 10 11 12 13 11 17 14 15 16 17 18 19 20 21 22 23 24 25 26 27 14 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 16 45 46 47 48 49 50 51 52 53 17 54 55 56 57 58 59 60 61 62 63 40 67 64 65 66 67 68 69 70 71 72 73 74 54 35 75 76 77 78 79 80 81 82 83 84 85 86 87 ...

output:

1406

result:

ok 1 number(s): "1406"

Test #9:

score: 0
Accepted
time: 127ms
memory: 32928kb

input:

7
142857
1 1 2 1 2 3 4 4 8 5 6 7 8 9 10 11 12 13 14 7 15 15 16 17 18 19 20 21 22 23 24 25 26 27 28 17 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 14 55 56 57 58 59 60 61 62 63 27 69 43 64 65 66 67 68 69 70 71 72 73 57 15 74 75 76 77 78 79 80 81 82 83 84 85 86 36 87 ...

output:

528
527
526
527
527
527
527

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 110ms
memory: 31132kb

input:

10
100000
1 1 2 2 2 3 4 5 6 7 8 6 8 9 10 11 12 13 14 15 16 17 22 18 19 20 21 22 23 8 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 27 39 40 41 42 43 44 45 46 39 39 48 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 59 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89...

output:

439
439
441
439
441
441
442
441
441
440

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 112ms
memory: 30024kb

input:

15
66666
1 2 3 1 2 3 4 5 6 1 7 8 9 10 2 11 12 13 14 15 16 17 18 19 20 21 19 22 23 24 25 26 27 34 28 29 30 31 32 33 34 10 35 36 37 38 39 40 41 42 22 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 57 20 62 63 64 65 66 67 68 69 70 71 77 72 73 74 75 76 77 78 79 80 81 82 83 77 84 85 86 87 88 89...

output:

360
358
359
359
359
359
359
360
359
360
359
361
358
360
359

result:

ok 15 numbers

Test #12:

score: 0
Accepted
time: 76ms
memory: 27964kb

input:

57
17543
1 1 2 2 3 5 4 5 6 3 7 8 9 10 3 1 4 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 25 32 33 34 35 36 37 38 39 3 40 41 42 43 44 45 46 47 48 6 49 50 51 52 53 54 55 56 57 58 26 59 60 61 62 63 64 65 66 67 68 69 69 17 70 71 72 73 74 75 76 77 78 79 80 81 54 82 83 84 85 86 87 88 89 ...

output:

181
182
181
182
182
183
183
183
182
183
183
182
181
184
183
183
182
181
181
183
182
183
181
183
182
182
182
183
183
183
180
182
183
183
182
181
181
181
183
183
182
182
180
182
181
183
182
182
183
183
183
181
180
181
181
182
183

result:

ok 57 numbers

Test #13:

score: 0
Accepted
time: 65ms
memory: 27796kb

input:

100
10000
1 2 2 2 3 5 3 4 5 6 7 8 9 10 11 12 13 14 15 9 8 16 17 18 19 20 2 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 11 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 3 49 19 21 13 61 62 63 64 65 66 67 68 69 20 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 8...

output:

136
138
138
136
135
137
136
136
137
138
137
137
138
138
138
137
137
137
138
137
137
136
138
136
138
138
138
137
137
138
137
136
136
137
137
137
137
138
137
136
137
138
136
136
138
138
136
137
137
138
136
137
137
138
137
138
137
138
136
135
138
137
136
137
134
137
137
136
137
137
135
136
138
138
136
...

result:

ok 100 numbers

Test #14:

score: 0
Accepted
time: 59ms
memory: 27448kb

input:

1000
1000
1 1 2 3 5 4 5 5 9 6 7 8 9 10 11 12 13 17 9 14 15 16 17 18 1 19 20 21 22 23 24 25 3 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 30 43 44 45 46 47 48 49 50 51 8 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 70 71 50 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 9...

output:

43
42
42
42
41
41
42
41
42
42
41
42
42
42
42
41
42
41
42
42
42
41
42
41
42
42
42
40
43
40
42
42
40
42
42
42
41
41
42
41
41
41
42
42
42
41
42
41
42
42
42
42
42
42
41
42
43
41
40
41
42
42
42
43
42
40
41
42
42
41
41
41
42
42
43
41
41
41
42
40
42
42
42
42
41
42
42
42
42
43
41
41
42
41
41
41
42
42
42
42
...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 53ms
memory: 27284kb

input:

10000
100
1 1 3 2 2 3 4 5 7 6 7 8 9 10 11 12 13 14 4 2 10 15 16 17 18 19 5 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 23 46 47 48 49 50 51 52 53 54 16 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 13 37 49 76 77 78 79 80 81 82 83 84 85 86
100
1 2 2...

output:

12
12
13
12
12
12
12
11
12
12
12
12
13
13
12
12
12
11
13
13
12
12
13
12
12
12
12
13
13
13
12
12
12
13
11
13
13
12
12
12
13
12
12
12
12
12
12
12
12
11
12
13
11
13
12
12
12
12
12
12
12
13
12
12
12
11
12
12
13
13
12
13
12
13
12
11
12
11
11
12
13
12
13
12
12
13
12
12
12
12
12
12
12
12
12
12
12
11
12
13
...

result:

ok 10000 numbers

Test #16:

score: 0
Accepted
time: 54ms
memory: 27352kb

input:

100000
10
1 2 1 2 3 4 5 6 7
10
1 1 1 2 3 6 4 5 6
10
1 1 3 2 3 1 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 2 3 1 2 3 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 1 2 4 3 4 5 6 7
10
1 1 1 2 3 4 5 6 7
10
1 2 2 4 3 3 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 1 3 2 3 6 4 5 6
10
1 2 2 4 3 2 4 5 6
10
1 1 1 2 3 5 4 5 6
10
1 2 2 4 3 4 5 6 7...

output:

3
4
4
3
3
3
3
3
3
3
4
3
4
3
4
4
3
3
3
3
3
4
4
4
4
3
3
3
3
3
4
4
4
4
3
3
3
3
3
4
3
4
4
3
3
4
3
3
4
3
4
3
3
3
3
3
4
3
3
3
3
4
3
3
3
3
3
4
3
3
4
3
4
4
3
3
4
3
3
4
3
3
3
4
4
3
3
3
3
3
4
3
4
4
3
3
3
3
4
3
4
3
3
4
3
3
4
3
4
4
3
3
4
4
4
3
3
3
3
3
4
3
3
3
4
3
4
3
3
3
3
4
3
4
3
4
3
4
3
4
3
3
3
4
4
3
4
4
3
3
...

result:

ok 100000 numbers
English 繁體中文 简体中文

伺服器時間: 2025-02-01 21:46:15 | 開源專案