Submission #1259259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259259		SDAdzs1tg	Biochips (IZhO12_biochips)	C++20	100 / 100	374 ms	406480 KiB

biochips

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
vector<int> adj[maxn];
int n, m, in[maxn], out[maxn], cnt = 0;
int a[maxn];
vector<int> x;
void dfs(int u, int p) {
	in[u] = ++cnt;
	x.push_back(u);
	for(auto v : adj[u]) {
		if(v == p) continue;
		dfs(v, u);
	}
	out[u] = cnt;
}
int dp[maxn][510];
signed main () {
	cin >> n >> m;
	int root = 0;
	for(int i = 1; i <= n; i++) {
		int v, c; cin >> v >> c;
		if(v == 0) {
			root = i;
			continue;
		}
		adj[v].push_back(i);
		a[i] = c;
	}
	x.push_back(0);
	dfs(root, -1);
	for(int i = 0; i <= n + 1; i++) {
		for(int j = 1; j <= m; j++) dp[i][j] = -1e18;
	}
	for(int i = x.size() - 1; i >= 0; i--) {
		int t = x[i];
		for(int j = 1; j <= m; j++) {
			dp[i][j] = max(dp[i][j], dp[i + 1][j]);
			dp[i][j] = max(dp[i][j], dp[out[t] + 1][j - 1] + a[t]);
		}
	}
	cout << dp[1][m];
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:33:56: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   33 |                 for(int j = 1; j <= m; j++) dp[i][j] = -1e18;
      |                                                        ^~~~~

• Subtask 1: 100 / 100