QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745422#9751. 覆盖一棵树hhoppitree#RE 12ms5012kbC++17594b2024-11-14 09:50:072024-11-14 09:50:10

Judging History

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

  • [2024-11-14 09:50:10]
  • 评测
  • 测评结果：RE
  • 用时：12ms
  • 内存：5012kb
查看
  • [2024-11-14 09:50:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int fa[N], f[N], g[N];

signed main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 2; i <= n; ++i) {
            scanf("%d", &fa[i]);
        }
        for (int i = 1; i <= n; ++i) f[i] = 0, g[i] = 1e9;
        int res = 0;
        for (int i = n; i >= 1; --i) {
            f[i] = (g[i] > n ? 0 : g[i]) + (i != 1);
            res = max(res, f[i]), g[fa[i]] = min(g[fa[i]], f[i]);
        }
        printf("%d\n", res);
    }
    return 0;
}
源文件, 语言: C++17

详细

Test #1:

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

input:

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

output:

3
7

result:

ok 2 lines

Test #2:

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

input:

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

output:

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

result:

ok 33428 lines

Test #3:

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

input:

3934
19
1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18
65
1 2 3 4 5 5 7 8 9 10 11 12 12 14 15 16 17 18 19 19 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 39 41 42 43 44 44 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 60 62 63 63
66
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 21 22 2...

output:

11
20
24
28
10
23
5
31
8
19
7
14
1
15
14
14
15
9
11
10
11
13
5
31
23
9
11
23
32
18
17
18
10
14
1
24
1
28
18
13
9
10
9
12
24
5
27
27
9
29
15
17
23
20
17
11
14
12
19
9
19
13
17
16
14
7
17
23
5
20
11
14
8
9
18
2
9
16
29
17
2
31
13
14
3
16
9
26
14
15
13
5
17
18
19
24
12
20
10
10
13
14
13
2
12
10
15
18
1...

result:

ok 3934 lines

Test #4:

score: 0
Accepted
time: 10ms
memory: 3836kb

input:

386
208
1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

27
31
36
29
27
27
23
31
27
30
25
28
37
14
27
23
35
30
32
52
38
58
31
34
28
43
37
39
32
33
22
34
28
27
39
25
25
45
32
23
25
47
24
48
28
34
45
22
26
37
13
32
32
24
40
22
26
33
23
25
31
21
19
45
9
24
23
27
27
32
40
15
22
33
21
44
36
29
24
28
44
43
23
43
31
19
36
33
50
22
18
20
9
41
34
58
22
25
21
18
34...

result:

ok 386 lines

Test #5:

score: 0
Accepted
time: 10ms
memory: 4028kb

input:

42
8830
1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

65
52
46
34
42
48
35
40
40
43
42
46
44
44
52
39
54
37
43
29
40
38
45
43
51
48
35
37
56
48
47
37
30
42
42
32
43
56
53
53
48
37

result:

ok 42 lines

Test #6:

score: 0
Accepted
time: 12ms
memory: 5012kb

input:

5
51400
1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

65
58
58
37
57

result:

ok 5 lines

Test #7:

score: -100
Runtime Error

input:

2
56002
1 2 3 3 4 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 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 70 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 100 ...

output:

result:
English 繁體中文 简体中文

服务器时间: 2025-01-21 06:00:47 | 开源项目