oj.uz

답안 #508215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
508215 2022-01-13T07:23:12 Z sidon 바이오칩 (IZhO12_biochips) C++17
100 / 100
 422 ms 396580 KB 
#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

# 결과 실행 시간 메모리 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