제출 #386602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386602		milleniumEeee	바이오칩 (IZhO12_biochips)	C++17	100 / 100	763 ms	413420 KiB

biochips

#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 / 100