QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#757662#9751. 覆盖一棵树Jumping#AC ✓16ms31728kbC++141.3kb2024-11-17 11:56:242024-11-17 11:56:26

Judging History

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

  • [2024-11-17 11:56:26]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:31728kb
  • [2024-11-17 11:56:24]
  • 提交

answer

#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define ll long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-8;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){
	bool f=0;int x=0;char ch;
	ch=gt();
	while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}
	while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}
	if(f)return -x;
	else return x;
}
template<class T>
inline void print(T x){
	char s[114];
	int top=0;
	if(x<0)pt('-');
	do{
		top++;
		if(x>=0)s[top]=(x%10)+48;
		else s[top]=(-(x%10)+48);
		x/=10;
	}while(x);
	while(top){pt(s[top]);top--;}
}
const int MAXN=2e5+10;
vector<int>g[MAXN];
void add_edge(int u,int v){
	g[u].push_back(v);
}
int dp[MAXN],ans=-1;
int outd[MAXN];
void dfs(int u,int fa){
	if(!outd[u]){
		dp[u]=0;
		return;
	}
	for(int v:g[u]){
		if(v==fa)continue;
		dfs(v,u);
		dp[u]=min(dp[u],dp[v]+1);
		ans=max(ans,dp[v]+1);
	}
}
void solve(){
	ans=-1;
	int n=read();for(int i=0;i<=n;i++)outd[i]=0,dp[i]=INT_MAX;
	for(int i=2;i<=n;i++){
		int p=read();
		add_edge(p,i);
		outd[p]++;
	}
	add_edge(1,0); 
	dfs(1,0);
	cout<<ans<<'\n';for(int i=0;i<=n;i++)g[i].clear();
	
}
signed main(){
	int T=read();
	while(T--)solve();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9424kb

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: 6ms
memory: 8364kb

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: 6ms
memory: 8300kb

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

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: 8ms
memory: 9584kb

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: 6ms
memory: 18696kb

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: 10ms
memory: 24372kb

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: 8ms
memory: 25400kb

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

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:

8

result:

ok single line: '8'

Test #10:

score: 0
Accepted
time: 7ms
memory: 11036kb

input:

1
200000
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 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39...

output:

2

result:

ok single line: '2'

Test #11:

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

input:

1
200000
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:

247

result:

ok single line: '247'

Test #12:

score: 0
Accepted
time: 7ms
memory: 10992kb

input:

1
200000
1 1 1 1 1 1 1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 1 1 1 133 133 133 133 133 133 133...

output:

2

result:

ok single line: '2'

Test #13:

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

input:

1
200000
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:

161

result:

ok single line: '161'

Test #14:

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

input:

2
100000
1 2 3 4 3 6 3 3 9 3 11 12 13 3 15 15 15 2 19 2 2 2 1 24 25 26 27 28 29 30 30 29 27 27 35 36 37 38 27 27 41 42 42 26 45 46 47 47 49 50 51 46 53 53 46 56 46 58 58 60 61 61 63 60 65 65 60 68 58 70 70 72 70 74 74 76 74 78 79 79 78 82 78 84 78 74 87 88 89 90 74 74 93 58 46 96 97 98 98 98 101 102...

output:

7
7

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 3ms
memory: 9344kb

input:

100000
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2...

output:

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
1
1
1
1
1
...

result:

ok 100000 lines

Test #16:

score: 0
Accepted
time: 4ms
memory: 10348kb

input:

1
200000
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 1...

output:

1

result:

ok single line: '1'

Test #17:

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

input:

1
200000
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:

199999

result:

ok single line: '199999'

Extra Test:

score: 0
Extra Test Passed