oj.uz

Submission #21868

# Submission time Handle Problem Language Result Execution time Memory
21868 2017-04-26T14:46:20 Z ulna Biochips (IZhO12_biochips) C++11
100 / 100
 446 ms 444604 KB 
#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; i++) if (~dp[dfn[u]][i]) {
			dp[r[u]][i + 1] = max(dp[r[u]][i + 1], dp[dfn[u]][i] + x[u]);
		}

		for (int i = 0; i <= m; i++) {
			dp[dfn[u] + 1][i] = max(dp[dfn[u] + 1][i], dp[dfn[u]][i]);
		}	
	}

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

	return 0;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 442768 KB Output is correct
2 Correct 19 ms 442768 KB Output is correct
3 Correct 29 ms 442768 KB Output is correct
4 Correct 36 ms 442900 KB Output is correct
5 Correct 59 ms 442900 KB Output is correct
6 Correct 33 ms 442900 KB Output is correct
7 Correct 263 ms 444404 KB Output is correct
8 Correct 279 ms 444404 KB Output is correct
9 Correct 353 ms 444528 KB Output is correct
10 Correct 446 ms 444604 KB Output is correct