Submission #21867

#	Time	Username	Problem	Language	Result	Execution time	Memory
21867		ulna	Biochips (IZhO12_biochips)	C++11	0 / 100	43 ms	442768 KiB

biochips

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

// why am I so weak

int n, m;
int x[200055];
vector<int> g[200055];

int t, dfn[200055], r[200055];

int dp[200055][555];

void dfs(int v) {
	dfn[v] = t++;

	for (auto u : g[v]) {
		dfs(u);
	}

	r[v] = t;
}
int main() {
	scanf("%d %d", &n, &m);

	int root = -1;

	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--;

		x[i] = b;

		if (~a) g[a].push_back(i);
		else root = i;
	}

	dfs(root);

	vector<int> vec(n);

	for (int i = 0; i < n; i++) vec[i] = i;

	sort(vec.begin(), vec.end(), [&] (int u, int v) {
		return dfn[u] < dfn[v];
	});

	memset(dp, -1, sizeof(dp));

	dp[0][0] = 0;
	
	for (auto u : vec) {
		for (int i = 0; i <= m && dfn[u] > 0; i++) dp[dfn[u]][i] = max(dp[dfn[u]][i], dp[dfn[u] - 1][i]);
		for (int i = 0; i < m; i++) if (~dp[dfn[u]][i]) {
			dp[r[u]][i + 1] = max(dp[r[u]][i + 1], dp[dfn[u]][i] + x[u]);
		}
	}

	printf("%d\n", dp[n][m]);

	return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:24:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
biochips.cpp:30:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
                         ^

• Subtask 1: 0 / 100