Submission #4807

#	Time	Username	Problem	Language	Result	Execution time	Memory
4807		tncks0121	Biochips (IZhO12_biochips)	C++98	100 / 100	420 ms	405404 KiB

biochips

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 200005;
const int M_ = 505;

int N, M;
vector<int> Gph[N_];
int V[N_];
int root;

int TIME;
int in[N_], out[N_];
vector<int> ord;

void DFS (int u) {
	if(Gph[u].empty()) ++TIME;
	in[u] = TIME;
	for(int e = 0; e < Gph[u].size(); e++) {
		int v = Gph[u][e];
		DFS(v);
	}
	out[u] = TIME;
	ord.push_back(u);
}

int Table[N_][M_];
int res;
int main() {
	int i, j, k;
	
	scanf("%d%d", &N, &M);
	for(i = 1; i <= N; i++) {
		int p; scanf("%d%d", &p, V+i);
		if(p == 0) root = i;
		else Gph[p].push_back(i);
	}

	DFS(root);

	for(i = 0; i < N; i++) {
		int u = ord[i];
		int l = in[u], r = out[u];
		for(j = 1; j <= M; j++) Table[r][j] = max(Table[r][j], Table[r-1][j]);
		for(j = 1; j <= M && j <= l; j++) Table[r][j] = max(Table[r][j], Table[l - 1][j - 1] + V[u]);
	}

	for(i = 1; i <= TIME; i++) res = max(res, Table[i][M]);

	printf("%d\n", res);

	return 0;
}

• Subtask 1: 100 / 100