Submission #344772

#	Time	Username	Problem	Language	Result	Execution time	Memory
344772		Gurban	Biochips (IZhO12_biochips)	C++17	0 / 100	30 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],cnt;
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];
	if(E[nd].empty()){
		l[nd]=nd,r[nd]=nd; cnt++;
		v.push_back(nd); ps[nd] = (int)v.size()-1;
		return;
		
	}
	for(auto i : E[nd]){
		dfs(i);
		if(l[nd] == 0) l[nd] = l[i];
		r[nd] = r[i];
		mx[nd] = max(mx[nd],mx[i]);
	}
}

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(cnt >= 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