Submission #4809

#	Time	Username	Problem	Language	Result	Execution time	Memory
4809		cki86201	Biochips (IZhO12_biochips)	C++98	100 / 100	364 ms	402884 KiB

biochips

#include<stdio.h>
#include<algorithm>
using namespace std;

int N,M;
int dp[200020][505];
int me[200020],S[200020],D[200020],ord[200020],now = 1;
int st[200020],en[400040],next[400040],c_edge = 2,R;
bool chk[200020];

void addedge(int s,int d)
{
	next[c_edge]=st[s];
	st[s]=c_edge;
	en[c_edge++]=d;
}

void dfs(int x)
{
	chk[x]=1;
	S[x] = now;
	for(int i=st[x];i;i=next[i]){
		if(!chk[en[i]])dfs(en[i]);
	}
	ord[D[x] = now++] = x;
}

int main(){
	scanf("%d%d",&N,&M);
	int i,j;
	for(i=1;i<=N;i++){
		int x;
		scanf("%d%d",&x,me+i);
		if(x)addedge(x,i),addedge(i,x);
		else R = i;
	}
	dfs(R);
	for(i=1;i<=M;i++)dp[0][i]=-1e9;
	for(i=1;i<=N;i++){
		int t = ord[i];
		for(j=1;j<=M;j++)dp[t][j] = dp[ord[i-1]][j];
		for(j=1;j<=M;j++)dp[t][j] = max(dp[t][j], dp[ord[S[t]-1]][j-1]+me[t]);
	}
	printf("%d",dp[R][M]);
	return 0;
}

• Subtask 1: 100 / 100