oj.uz

Submission #4809

# Submission time Handle Problem Language Result Execution time Memory
4809 2014-01-04T11:02:43 Z cki86201 Biochips (IZhO12_biochips) C++
100 / 100
 364 ms 402884 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 402884 KB Output is correct
2 Correct 0 ms 402884 KB Output is correct
3 Correct 0 ms 402884 KB Output is correct
4 Correct 0 ms 402884 KB Output is correct
5 Correct 8 ms 402884 KB Output is correct
6 Correct 12 ms 402884 KB Output is correct
7 Correct 188 ms 402884 KB Output is correct
8 Correct 216 ms 402884 KB Output is correct
9 Correct 252 ms 402884 KB Output is correct
10 Correct 364 ms 402884 KB Output is correct