Submission #344778

#	Time	Username	Problem	Language	Result	Execution time	Memory
344778		Gurban	Biochips (IZhO12_biochips)	C++17	0 / 100	31 ms	10092 KiB

biochips

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

using ll = long long;

const int N = 505;
const int maxn=200005;
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],l[nd]=r[nd]=nd;
	for(auto i : E[nd]){
		dfs(i);
		if(l[nd] == nd) l[nd] = l[i];
		r[nd] = r[i];
		mx[nd] = max(mx[nd],mx[i]);
	}
	if(E[nd].empty()) 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[lft][i-1]+mx[nd],dp[pos][i]);
	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);
	
	assert((int)v.size()-1 >= m);
	
	for(int i = 0;i < (int)v.size();i++) for(int j = 1;j <= m;j++) dp[i][j] = -1e9;

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

• Subtask 1: 0 / 100