oj.uz

Submission #508241

# Submission time Handle Problem Language Result Execution time Memory
508241 2022-01-13T07:40:55 Z sidon Biochips (IZhO12_biochips) C++17
100 / 100
 498 ms 395164 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 13 ms 13896 KB Output is correct
5 Correct 17 ms 18320 KB Output is correct
6 Correct 17 ms 18252 KB Output is correct
7 Correct 319 ms 294856 KB Output is correct
8 Correct 390 ms 294920 KB Output is correct
9 Correct 450 ms 357708 KB Output is correct
10 Correct 498 ms 395164 KB Output is correct