QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750307#9751. 覆盖一棵树diandian2020#WA 12ms4940kbC++14681b2024-11-15 14:00:362024-11-15 14:00:45

Judging History

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

  • [2024-11-15 14:00:45]
  • 评测
  • 测评结果：WA
  • 用时：12ms
  • 内存：4940kb
查看
  • [2024-11-15 14:00:36]
  • 提交

answer

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=2e5+9;
int p[N]; bool leaf[N],vis[N];
void solve(){
	int n; scanf("%d",&n);
	for(int i=1;i<=n;i++) leaf[i]=vis[i]=0; vis[1]=1;
	for(int i=2;i<=n;i++) scanf("%d",&p[i]),leaf[p[i]]=1;
	int res=0;
	for(int i=1;i<=n;i++) if(!leaf[i]){
		int t=0,x=i;
		while(!vis[x]) vis[x]=1,t++,x=p[x];
		res=max(res,t);
	}
	printf("%d\n",res);
}
int main(){
	int T=1;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}
/*
1
4 17
3 2 5 16
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3960kb

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: 3812kb

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: 3908kb

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: 3952kb

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: 11ms
memory: 4448kb

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

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:

119
105

result:

ok 2 lines

Test #8:

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

input:

2
56002
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 100 ...

output:

56001
143997

result:

ok 2 lines

Test #9:

score: -100
Wrong Answer
time: 12ms
memory: 4940kb

input:

1
200000
1 2 2 4 4 6 7 8 8 8 11 12 8 7 7 7 17 6 19 19 6 4 4 24 25 25 27 27 29 24 31 31 31 34 4 36 36 2 39 40 39 39 43 44 45 46 47 48 47 47 51 52 45 54 45 56 57 56 59 45 61 62 61 64 64 66 45 68 69 69 71 71 73 73 69 76 77 78 78 68 68 82 68 45 85 85 87 85 89 90 91 91 90 94 94 90 89 98 98 100 101 102 98...

output:

11

result:

wrong answer 1st lines differ - expected: '8', found: '11'
English 繁體中文 简体中文

Server Time: 2025-01-20 20:00:40 | OpenSource Project