oj.uz

Submission #16896

# Submission time Handle Problem Language Result Execution time Memory
16896 2015-10-24T13:15:15 Z erdemkiraz Biochips (IZhO12_biochips) C++
100 / 100
 558 ms 405132 KB 
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 2e5 + 5;
const int M = 500 + 5;

int n, m, tick, root;
int st[N], nd[N], ord[N], a[N], dp[M][N];
vector < int > v[N];

void dfs(int x) {
    st[x] = ++tick;
    foreach(it, v[x]) {
        int u = *it;
        dfs(u);
    }
    nd[x] = tick;
}

bool cmp(int x, int y) {
    return st[x] < st[y];
}

int main() {

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i++) {
        int x;
        scanf("%d %d", &x, a + i);
        if(!x) {
            root = i;
        }
        v[x].push_back(i);
        ord[i] = i;
    }

    dfs(root);

    sort(ord + 1, ord + n + 1, cmp);

    for(int i = 1; i <= m; i++) {
        for(int j = n; j >= 1; j--) {
            int x = ord[j];
            dp[i][j] = max(dp[i][j + 1], dp[i - 1][nd[x] + 1] + a[x]);
        }
        dp[i][n + 1] = -inf;
    }

    printf("%d\n", dp[m][1]);

    return 0;

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 404076 KB Output is correct
2 Correct 3 ms 404076 KB Output is correct
3 Correct 0 ms 404076 KB Output is correct
4 Correct 14 ms 404208 KB Output is correct
5 Correct 15 ms 404076 KB Output is correct
6 Correct 9 ms 404076 KB Output is correct
7 Correct 357 ms 405132 KB Output is correct
8 Correct 357 ms 405132 KB Output is correct
9 Correct 387 ms 405000 KB Output is correct
10 Correct 558 ms 405000 KB Output is correct