Submission #1260253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260253		proofy	Biochips (IZhO12_biochips)	C++20	100 / 100	301 ms	394872 KiB

biochips

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	vector<int> p(n, -1), x(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i] >> x[i];
		--p[i];
		if (p[i] >= 0) g[p[i]].push_back(i);
	}

	vector<int> tin(n), tout(n), vertex(n);
	int timer = 0;
	auto dfs = [&](auto self, int v) -> void {
		tin[v] = timer++;
		vertex[tin[v]] = v;
		for (int u : g[v]) self(self, u);
		tout[v] = timer;
	};
	for (int i = 0; i < n; i++) if (p[i] == -1) dfs(dfs, i);

	vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1e9));
	dp[n][0] = 0;

	for (int i = n - 1; i >= 0; --i) 
		for (int j = m; j >= 0; --j) {
			int v = vertex[i];
			dp[i][j] = dp[i + 1][j];
			if (j >= 1) dp[i][j] = max(dp[i][j], dp[tout[v]][j - 1] + x[v]);
		}
	
	cout << dp[0][m] << "\n";
}

• Subtask 1: 100 / 100