Submission #508215

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
508215	2022-01-13T07:23:12 Z	sidon	Biochips (IZhO12_biochips)	C++17	100 / 100	422 ms	396580 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5016 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	5196 KB	Output is correct
4	Correct	12 ms	13960 KB	Output is correct
5	Correct	14 ms	18372 KB	Output is correct
6	Correct	19 ms	18212 KB	Output is correct
7	Correct	363 ms	296412 KB	Output is correct
8	Correct	333 ms	296352 KB	Output is correct
9	Correct	344 ms	359040 KB	Output is correct
10	Correct	422 ms	396580 KB	Output is correct