oj.uz

Submission #930942

# Submission time Handle Problem Language Result Execution time Memory
930942 2024-02-20T21:06:28 Z NintsiChkhaidze Cat in a tree (BOI17_catinatree) C++17
51 / 100
 9 ms 31584 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
using namespace std;
 
const int N = 5e3 + 5;
vector <int> v[N];
int dp[N][N],dpnew[N],K;

int dfs(int x,int par){
	dp[x][0] = 1;
	int s = 1;

	int mx = 0;
	for (int to: v[x]){
		int y1 = dfs(to,x);
		s = max(s,y1 + 1);

		for (int i = 0; i <= mx; i++){
			for (int j = 0; j <= y1; j++){
				int dist = i + j + 1;
				if (dist < K) continue;
				dpnew[min(i,j + 1)] = max(dpnew[min(i,j + 1)],dp[x][i] + dp[to][j]);
			}
		}

		for (int j = 0; j <= y1; j++)
			dpnew[j + 1] = max(dpnew[j + 1],dp[to][j]);
		
		mx=max(mx,y1);
		for (int j = 0; j <= mx; j++)
			dp[x][j] = max(dp[x][j],dpnew[j]),dpnew[j] = 0;
	}

	return s;
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n;
	cin>>n>>K;

	for (int i = 2; i <= n; i++){
		int par;
		cin>>par;
		v[par + 1].pb(i);
	}
	dfs(1,1);

	int ans=0;
	for (int i = 0; i <= n; i++){
		ans=max(ans,dp[1][i]);
	}
	cout<<ans<<endl;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2628 KB Output is correct
20 Correct 1 ms 2460 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2628 KB Output is correct
20 Correct 1 ms 2460 KB Output is correct
21 Correct 7 ms 31584 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 2 ms 10860 KB Output is correct
25 Correct 3 ms 21084 KB Output is correct
26 Correct 3 ms 21084 KB Output is correct
27 Correct 3 ms 21084 KB Output is correct
28 Correct 4 ms 31324 KB Output is correct
29 Correct 5 ms 31300 KB Output is correct
30 Correct 4 ms 31324 KB Output is correct
31 Correct 4 ms 31324 KB Output is correct
32 Correct 3 ms 29276 KB Output is correct
33 Correct 3 ms 29276 KB Output is correct
34 Correct 4 ms 29312 KB Output is correct
35 Correct 4 ms 29276 KB Output is correct
36 Correct 4 ms 31324 KB Output is correct
37 Correct 4 ms 31304 KB Output is correct
38 Correct 5 ms 31524 KB Output is correct
39 Correct 6 ms 31324 KB Output is correct
40 Correct 9 ms 31580 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2628 KB Output is correct
20 Correct 1 ms 2460 KB Output is correct
21 Correct 7 ms 31584 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 2 ms 10860 KB Output is correct
25 Correct 3 ms 21084 KB Output is correct
26 Correct 3 ms 21084 KB Output is correct
27 Correct 3 ms 21084 KB Output is correct
28 Correct 4 ms 31324 KB Output is correct
29 Correct 5 ms 31300 KB Output is correct
30 Correct 4 ms 31324 KB Output is correct
31 Correct 4 ms 31324 KB Output is correct
32 Correct 3 ms 29276 KB Output is correct
33 Correct 3 ms 29276 KB Output is correct
34 Correct 4 ms 29312 KB Output is correct
35 Correct 4 ms 29276 KB Output is correct
36 Correct 4 ms 31324 KB Output is correct
37 Correct 4 ms 31304 KB Output is correct
38 Correct 5 ms 31524 KB Output is correct
39 Correct 6 ms 31324 KB Output is correct
40 Correct 9 ms 31580 KB Output is correct
41 Runtime error 4 ms 1116 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -