oj.uz

Submission #16856

# Submission time Handle Problem Language Result Execution time Memory
16856 2015-10-23T16:48:07 Z murat Biochips (IZhO12_biochips) C++
80 / 100
 224 ms 402788 KB 
#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;

int w[N], val[N], n, m, x, y, start[N], finish[N], T, dp[N][501], root, p[N];
vector< int > v[N];

int dfs(int node) {
	start[node] = ++T;
	w[T] = node;
	foreach(it, v[node])
		dfs(*it);
	finish[node] = T;
}

int main() {
	scanf("%d %d", &n, &m);
	FOR(i, 1, n) {
		scanf("%d %d", &p[i], &val[i]);
		if(!p[i]) root = i;
		else v[p[i]].pb(i);
	} dfs(root);
	FOR(i, 0, m) dp[n+1][i] = -inf;
	ROF(i, n, 1)
		FOR(j, 0, m) 
			dp[i][j] = max(dp[i+1][j], (j != 0) * (dp[finish[w[i]] + 1][j-1] + val[w[i]]));		
	cout << dp[1][m] << endl; 
	return 0;
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 401732 KB Output isn't correct
2 Incorrect 0 ms 401732 KB Output isn't correct
3 Correct 0 ms 401732 KB Output is correct
4 Correct 0 ms 401864 KB Output is correct
5 Correct 11 ms 401732 KB Output is correct
6 Correct 0 ms 401732 KB Output is correct
7 Correct 160 ms 402788 KB Output is correct
8 Correct 126 ms 402788 KB Output is correct
9 Correct 193 ms 402656 KB Output is correct
10 Correct 224 ms 402656 KB Output is correct