Submission #1259256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259256		SDAdzs1tg	Biochips (IZhO12_biochips)	C++20	60 / 100	304 ms	589824 KiB

biochips

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
vector<int> adj[maxn];
int n, m, in[maxn], out[maxn], cnt = 0;
int a[maxn];
vector<int> x;
void dfs(int u, int p) {
	in[u] = ++cnt;
	x.push_back(u);
	for(auto v : adj[u]) {
		if(v == p) continue;
		dfs(v, u);
	}
	out[u] = cnt;
}
int dp[maxn][510];
struct st{
	int l, r, c;
};
bool cmp(st a, st b) {
	return a.r < b.r;
}
st d[maxn];
signed main () {
	cin >> n >> m;
	int root = 0;
	for(int i = 1; i <= n; i++) {
		int v, c; cin >> v >> c;
		if(v == 0) {
			root = i;
			continue;
		}
		adj[i].push_back(v);
		adj[v].push_back(i);
		a[i] = c;
	}
	x.push_back(0);
	dfs(root, -1);
	for(int i = 1; i <= n; i++) {
		d[i] = {in[i], out[i], a[i]};
	}
	for(int i = 0; i <= n + 1; i++) {
		for(int j = 1; j <= m; j++) dp[i][j] = -1e18;
	}
	for(int i = x.size() - 1; i >= 0; i--) {
		int t = x[i];
		for(int j = 1; j <= m; j++) {
			dp[i][j] = max(dp[i][j], dp[i + 1][j]);
			dp[i][j] = max(dp[i][j], dp[out[t] + 1][j - 1] + a[t]);
		}
	}
	cout << dp[1][m];
}

• Subtask 1: 60 / 100