oj.uz

Submission #344785

# Submission time Handle Problem Language Result Execution time Memory
344785 2021-01-06T14:40:45 Z nandonathaniel Biochips (IZhO12_biochips) C++14
0 / 100
 2000 ms 414572 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);
	memset(dp,-1,sizeof(dp));
	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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 400364 KB Output is correct
2 Correct 211 ms 400348 KB Output is correct
3 Correct 203 ms 400388 KB Output is correct
4 Correct 225 ms 401132 KB Output is correct
5 Correct 227 ms 401260 KB Output is correct
6 Correct 236 ms 401132 KB Output is correct
7 Correct 1339 ms 411808 KB Output is correct
8 Correct 1327 ms 411668 KB Output is correct
9 Correct 1621 ms 413384 KB Output is correct
10 Execution timed out 2074 ms 414572 KB Time limit exceeded