Submission #508241

#	Time	Username	Problem	Language	Result	Execution time	Memory
508241		sidon	Biochips (IZhO12_biochips)	C++17	100 / 100	498 ms	395164 KiB

biochips

#include <bits/stdc++.h>
using namespace std;

const int Z = 2e5+1;

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

#define pull for(int i = M + 1; --i; ) dp[r][i] = max(dp[r][i], dp

void dfs(int u) {
	int l = r;
	if(empty(g[u])) {
		++r;
		pull [r-1][i]);
	}
	for(int v : g[u]) dfs(v);

	pull [l][i-1] + S[u]);
}

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

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

• Subtask 1: 100 / 100