Submission #508215

#	Time	Username	Problem	Language	Result	Execution time	Memory
508215		sidon	Biochips (IZhO12_biochips)	C++17	100 / 100	422 ms	396580 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
#define maxim(X, Y) (X = max(X, Y))

const int Z = 2e5+1;

int N, M, S[Z], rt, dp[Z][501], r;
vector<int> g[Z];

void dfs(int u) {
	int l = r;
	if(empty(g[u])) {
		++r;
		for(int i = 0; i <= M; i++)
			maxim(dp[r][i], dp[r-1][i]);
	}
	for(int v : g[u]) dfs(v);
	
	for(int i = M + 1; u != rt && --i; )
		maxim(dp[r][i], dp[l][i-1] + S[u]);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> N >> M;
	for(int i=1; i<=N; ++i) {
		int p; cin >> p >> S[i];
		if(p) g[p].push_back(i);
		else rt = i;
	}

	dfs(rt);

	cout << *max_element(dp[r], dp[r] + M + 1);
}

• Subtask 1: 100 / 100