Submission #81146

#	Time	Username	Problem	Language	Result	Execution time	Memory
81146		wzy	Biochips (IZhO12_biochips)	C++11	100 / 100	642 ms	415200 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
#define time tr
#define pb push_back
int c[200005], r[200005], outfx[200005] , dp[200005][505];
vector<int> adj[200005];
int n , m , time = 0;
int root = -1;
int in[200005] , out[200005];
void solve(int x , int y){
	in[x] = ++time;
	r[in[x]] = c[x];
	dp[in[x]][1] = c[x];
	for(auto p : adj[x]){
		if(p == y) continue;
		solve(p, x);
	}
	out[in[x]] = time;
}

int32_t main(){
	scanf("%d%d" ,&n , &m);
	for(int i = 1 ; i <= n; i ++){
		int x , y;
		scanf("%d%d" , &x , &y);
		c[i] = y;
		if(x == 0) root = i;
		else{
			adj[x].pb(i);
			adj[i].pb(x);
		}
	}
	solve(root, root);
	int ans = 0;
	for(int i = time ; i >= 1 ; i--){
		for(int j = 1 ; j  <= m ; j++){
			if(i+1 <= time) dp[i][j] = max(dp[i][j], dp[i+1][j]);
			if(out[i] + 1 <= time){
			dp[i][j] = max(dp[i][j] , dp[out[i] + 1][j-1] + r[i]);
			}
			if(j == m) ans = max(ans , dp[i][j]);
		}
	}
	printf("%d\n" , ans);
}

Compilation message (stderr)

biochips.cpp: In function 'int32_t main()':
biochips.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" ,&n , &m);
  ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100