Submission #86914

#	Time	Username	Problem	Language	Result	Execution time	Memory
86914		Just_Solve_The_Problem	Biochips (IZhO12_biochips)	C++11	100 / 100	820 ms	409476 KiB

biochips

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

const int N = (int)2e5 + 7;
const int M = (int)500 + 7;

int n, m;
int pr[N], w[N];
vector < int > gr[N];
vector < int > order;
int tiktak;
int tin[N], tout[N];
int dp[N][M];

void dfs(int v) {
	if (gr[v].empty()) tiktak++;
	tin[v] = tiktak;
	for (int to : gr[v]) {
		dfs(to);
	}
	order.push_back(v);
	tout[v] = tiktak;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> pr[i] >> w[i];
		gr[pr[i]].push_back(i);
	}
	dfs(gr[0][0]);
	for (int i = 0; i < n; i++) {
		int v = order[i];
		int l = tin[v];
		int r = tout[v];
		for (int j = 0; j <= m; j++) {
			dp[r][j] = max(dp[r][j], dp[r - 1][j]);
		}
		for (int j = 1; j <= min(l, m); j++) {
			dp[r][j] = max(dp[r][j], dp[l - 1][j - 1] + w[v]);
		}
	}
	int res = 0;
	for (int i = 1; i <= tiktak; i++) {
		res = max(res, dp[i][m]);
	}
	cout << res;
}

Compilation message (stderr)

biochips.cpp:28:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 100 / 100