Submission #41325

#	Time	Username	Problem	Language	Result	Execution time	Memory
41325		wzy	Biochips (IZhO12_biochips)	C++14	0 / 100	5 ms	4984 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

int dp[200005][505] , c[200005] , n ,m;
vector<int> adj[200005];
int st[200005] , rv[200005] , ed[200005] , t = -1;
int root = -1;
void dfs(int x , int y){
	st[x] = ++t;
	for(int i = 0 ; i < adj[x].size() ; i++){
		int v = adj[x][i];
		if(y == v) continue;
		dfs(v , x);
	}
	ed[st[x]] = t;
	rv[st[x]] = x;
}


int main(){
	scanf("%d%d" , &n , &m);
	for(int i = 0 ; i <n;i++){
		int x , cy;
		scanf("%d%d" , &x , &cy);	
		c[i] = cy;
		if(x == 0){
			root = i;
			continue;
		}
		adj[i].pb(x-1);
		adj[x-1].pb(i);
	}
	dfs(root , root);
	for(int i = 0 ; i<= n ;i++)
		for(int j = 0 ; j <= m; j++) dp[i][j] = -100000000;
	dp[0][0] = 0;
	dp[1][ed[0]] = c[root];
	for(int i = 1 ; i <n ; i++){
		for(int j = 1 ; j <= m ; j++){
			int wut = 0;
			if(i) wut = dp[j-1][i-1];
			dp[j][ed[i]] = max(dp[j][ed[i]] , wut + c[rv[i]]);
		}
	}
	printf("%d\n" , dp[m][n-1]);
}

Compilation message (stderr)

biochips.cpp: In function 'void dfs(int, int)':
biochips.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[x].size() ; i++){
                    ^
biochips.cpp: In function 'int main()':
biochips.cpp:22:25: 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:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &x , &cy); 
                           ^

• Subtask 1: 0 / 100