Submission #344785

#	Time	Username	Problem	Language	Result	Execution time	Memory
344785		nandonathaniel	Biochips (IZhO12_biochips)	C++14	0 / 100	2074 ms	414572 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);
	memset(dp,-1,sizeof(dp));
	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: 0 / 100