Submission #344791

#	Time	Username	Problem	Language	Result	Execution time	Memory
344791		nandonathaniel	Biochips (IZhO12_biochips)	C++14	100 / 100	324 ms	401772 KiB

biochips

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005,MAXM=505;

int a[MAXN],idx,dp[MAXN][MAXM],preorder[MAXN],EN[MAXN],n;
vector<int> adj[MAXN];

void dfs(int now){
	idx++;
	preorder[idx]=now;
	for(auto nxt : adj[now]){
		dfs(nxt);
	}
	EN[now]=idx;
}

//int DP(int node,int sisa){
//	if(sisa<0)return -1e9;
//	if(node>n){
//		if(sisa==0)return 0;
//		else return -1e9;
//	}
//	int &ret=dp[node][sisa];
//	if(ret!=-1)return ret;
//	ret=DP(node+1,sisa);
//	ret=max(ret,a[preorder[node]]+DP(EN[preorder[node]]+1,sisa-1));
//	return ret;
//}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int m,p,root;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> p >> a[i];
		if(p==0)root=i;
		else adj[p].push_back(i);
	}
	dfs(root);
	for(int i=1;i<=m;i++)dp[n+1][i]=-1e9;
	for(int i=n;i>=1;i--){
		dp[i][0]=dp[i+1][0];
		for(int j=1;j<=m;j++){
			dp[i][j]=max(dp[i+1][j],a[preorder[i]]+dp[EN[preorder[i]]+1][j-1]);
		}
	}
	cout << dp[1][m] << '\n';
	return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:39:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |  dfs(root);
      |  ~~~^~~~~~

• Subtask 1: 100 / 100