Submission #344702

#	Time	Username	Problem	Language	Result	Execution time	Memory
344702		Gurban	Biochips (IZhO12_biochips)	C++17	0 / 100	220 ms	400492 KiB

biochips

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

using ll = long long;

const int N = 5e2+5;
const int maxn=2e5+5;
int n,m,root;
int p[maxn],a[maxn];
int mx[maxn],l[maxn],r[maxn];
vector<int>E[maxn],v;
int dp[maxn][N],ps[maxn];

void dfs(int nd){
	mx[nd] = a[nd];
	for(auto i : E[nd]){
		dfs(i);
		if(!l[nd]) l[nd] = l[i];
		r[nd] = r[i];
		mx[nd] = max(mx[nd],mx[i]);
	}
	if((int)E[nd].size() == 0){
		l[nd]=nd,r[nd]=nd;
		v.push_back(nd); ps[nd] = (int)v.size()-1;
	}
}

void f(int pos,int nd){
	if(nd == 0 or r[nd] != v[pos]) return;
	int lft = ps[l[nd]] - 1;
	for(int i = 1;i <= min(m,lft + 1);i++){
		dp[pos][i] = max(dp[pos][i],dp[lft][i]);
		if(dp[lft][i-1] != -1 and dp[lft][i-1] + mx[nd] > dp[pos][i]) dp[pos][i] = dp[lft][i-1]+mx[nd];
	}
	f(pos,p[nd]);
}

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

	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> p[i] >> a[i];
		if(p[i] == 0) root = i;
		else E[p[i]].push_back(i);
	}
	v.push_back(-1);
	dfs(root);

	memset(dp,-1,sizeof(dp));
	dp[0][0] = 0;

	for(int i = 1;i < (int)v.size();i++){
		dp[i][0] = 0;
		f(i,v[i]);
	}
	cout<<dp[(int)v.size()-1][m];
}

• Subtask 1: 0 / 100