oj.uz

Submission #344791

# Submission time Handle Problem Language Result Execution time Memory
344791 2021-01-06T14:46:23 Z nandonathaniel Biochips (IZhO12_biochips) C++14
100 / 100
 324 ms 401772 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 16 ms 22892 KB Output is correct
5 Correct 20 ms 25068 KB Output is correct
6 Correct 20 ms 25068 KB Output is correct
7 Correct 233 ms 299524 KB Output is correct
8 Correct 224 ms 299520 KB Output is correct
9 Correct 274 ms 364012 KB Output is correct
10 Correct 324 ms 401772 KB Output is correct