oj.uz

Submission #535804

# Submission time Handle Problem Language Result Execution time Memory
535804 2022-03-11T10:05:58 Z ngpin04 Cat in a tree (BOI17_catinatree) C++14
51 / 100
 10 ms 9336 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1505;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> adj[N];

int dp[N][N];
int n,d;

void dfs1(int u) {
	for (int v : adj[u])
		dfs1(v);

	dp[u][0] = 1;
	for (int v : adj[u])
		dp[u][0] += dp[v][d - 1];


	for (int i = 1; i <= d; i++) {
		int mx = 0;
		for (int v : adj[u]) {
			if (i <= (d >> 1)) {
				dp[u][i] += dp[v][d - i - 1];
				maxi(mx, dp[v][i - 1] - dp[v][d - i - 1]);
			} else {
				dp[u][i] += dp[v][i - 1];
			}
		}
		dp[u][i] += mx;
	}
			
	for (int i = d - 1; i >= 0; i--)
		maxi(dp[u][i], dp[u][i + 1]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> d;
	for (int i = 2; i <= n; i++) {
		int j; cin >> j;
		j++;
		adj[j].push_back(i);
	}

	if (n <= 1500 && d <= 1500) {
		dfs1(1);
		int ans = 0;
		for (int i = 0; i <= d; i++)
			maxi(ans, dp[1][i]);

		cout << ans;
	}

	return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 10 ms 9336 KB Output is correct
22 Correct 1 ms 2260 KB Output is correct
23 Correct 1 ms 2388 KB Output is correct
24 Correct 1 ms 2288 KB Output is correct
25 Correct 3 ms 4308 KB Output is correct
26 Correct 3 ms 4308 KB Output is correct
27 Correct 2 ms 4436 KB Output is correct
28 Correct 3 ms 6392 KB Output is correct
29 Correct 3 ms 6356 KB Output is correct
30 Correct 4 ms 6484 KB Output is correct
31 Correct 4 ms 6612 KB Output is correct
32 Correct 3 ms 6228 KB Output is correct
33 Correct 3 ms 6256 KB Output is correct
34 Correct 3 ms 5972 KB Output is correct
35 Correct 3 ms 5972 KB Output is correct
36 Correct 3 ms 6356 KB Output is correct
37 Correct 3 ms 6356 KB Output is correct
38 Correct 4 ms 6648 KB Output is correct
39 Correct 4 ms 6740 KB Output is correct
40 Correct 3 ms 6484 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 10 ms 9336 KB Output is correct
22 Correct 1 ms 2260 KB Output is correct
23 Correct 1 ms 2388 KB Output is correct
24 Correct 1 ms 2288 KB Output is correct
25 Correct 3 ms 4308 KB Output is correct
26 Correct 3 ms 4308 KB Output is correct
27 Correct 2 ms 4436 KB Output is correct
28 Correct 3 ms 6392 KB Output is correct
29 Correct 3 ms 6356 KB Output is correct
30 Correct 4 ms 6484 KB Output is correct
31 Correct 4 ms 6612 KB Output is correct
32 Correct 3 ms 6228 KB Output is correct
33 Correct 3 ms 6256 KB Output is correct
34 Correct 3 ms 5972 KB Output is correct
35 Correct 3 ms 5972 KB Output is correct
36 Correct 3 ms 6356 KB Output is correct
37 Correct 3 ms 6356 KB Output is correct
38 Correct 4 ms 6648 KB Output is correct
39 Correct 4 ms 6740 KB Output is correct
40 Correct 3 ms 6484 KB Output is correct
41 Runtime error 1 ms 596 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -