oj.uz

Submission #386602

# Submission time Handle Problem Language Result Execution time Memory
386602 2021-04-07T04:35:46 Z milleniumEeee Biochips (IZhO12_biochips) C++17
100 / 100
 763 ms 413420 KB 
#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define all(s) s.begin(), s.end()
#define szof(s) (int)s.size()
using namespace std;

const int MAXN = (int)2e5 + 5;
const int MAXM = (int)500 + 2;

vector <int> g[MAXN];
int cost[MAXN];
int dp[MAXN][MAXM];
int tin[MAXN], tout[MAXN], tiktak = 0;
int n, m;
int root = -1;
vector <int> sub[MAXN];
int DP[505][2];

void calc(int v) {
	memset(DP, -1, sizeof(DP));
	DP[0][0] = 0;
	int tp = 0;
	for (int to : sub[v]) {
		for (int i = 0; i <= m; i++) {
			DP[i][tp ^ 1] = DP[i][tp];
		}
		for (int cur = 1; cur <= m; cur++) {
			if (dp[to][cur] != -1) {
				for (int i = m; i >= 0; i--) {
					if (DP[i][tp] != -1 && i + cur <= m) {
						DP[i + cur][tp ^ 1] = max(DP[i + cur][tp ^ 1], DP[i][tp] + dp[to][cur]);
					}
				}
			}
		}
		tp ^= 1;
	}
}

void dfs(int v, int par) {
	if (v != root && szof(g[v]) == 1) { // leaf
		dp[v][1] = cost[v];
		return;
	}
	for (int to : g[v]) {
		if (to != par) {
			dfs(to, v);
			sub[v].pb(to);
		}
	}
	dp[v][1] = max(dp[v][1], cost[v]);
	for (int to : sub[v]) {
		dp[v][1] = max(dp[v][1], dp[to][1]);
	}
	calc(v);
	for (int k = 2; k <= m; k++) {
		dp[v][k] = max(DP[k][0], DP[k][1]);
	}
	sub[v].clear();
}

bool father(int a, int b) {
	return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}

signed main() {
	fastInp;
	cin >> n >> m;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++) {
		int par, x;
		cin >> par >> x;
		if (!par) {
			root = i;
		} else {
			g[par].pb(i);
			g[i].pb(par);
		}
		cost[i] = x;
	}
	dfs(root, -1);
	cout << max(0, dp[root][m]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 402668 KB Output is correct
2 Correct 187 ms 402796 KB Output is correct
3 Correct 188 ms 402668 KB Output is correct
4 Correct 200 ms 403328 KB Output is correct
5 Correct 202 ms 403308 KB Output is correct
6 Correct 204 ms 403308 KB Output is correct
7 Correct 469 ms 411372 KB Output is correct
8 Correct 462 ms 411500 KB Output is correct
9 Correct 626 ms 412652 KB Output is correct
10 Correct 763 ms 413420 KB Output is correct