Submission #16896

#	Time	Username	Problem	Language	Result	Execution time	Memory
16896		erdemkiraz	Biochips (IZhO12_biochips)	C++98	100 / 100	558 ms	405132 KiB

biochips

#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 / 100