oj.uz

Submission #4807

# Submission time Handle Problem Language Result Execution time Memory
4807 2014-01-04T09:32:09 Z tncks0121 Biochips (IZhO12_biochips) C++
100 / 100
 420 ms 405404 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 402780 KB Output is correct
2 Correct 0 ms 402780 KB Output is correct
3 Correct 0 ms 402780 KB Output is correct
4 Correct 8 ms 403052 KB Output is correct
5 Correct 4 ms 402916 KB Output is correct
6 Correct 8 ms 402916 KB Output is correct
7 Correct 272 ms 405400 KB Output is correct
8 Correct 248 ms 405404 KB Output is correct
9 Correct 348 ms 405344 KB Output is correct
10 Correct 420 ms 405344 KB Output is correct