Submission #659571

#	Time	Username	Problem	Language	Result	Execution time	Memory
659571		Vladth11	Biochips (IZhO12_biochips)	C++14	100 / 100	345 ms	405560 KiB

biochips

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const int base = 31;
const int NMAX = 200002;
const int INF = 1e9;
const int VMAX = 501;
const int nrbits = 17;
const int MOD = 1000000007;

int dp[NMAX][VMAX];
vector <int> g[NMAX];
int timp[NMAX];
int stamp;
int v[NMAX];
int m;
int root;

void maxSelf(int &x, int val){
    x = max(x, val);
}

void DFS(int node, int p){
    timp[node] = stamp;
    for(auto x : g[node]){
        if(x == p) continue;
        DFS(x, node);
    }
    ++stamp;
    for(int i = 0; i <= m; i++){
        dp[stamp][i] = dp[stamp - 1][i];
    }
    for(int i = 1; i <= m; i++){
        maxSelf(dp[stamp][i], dp[timp[node]][i - 1] + v[node]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n >> m;
    for(int i = 0; i <= m; i++)
        dp[0][i] = -INF;
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p >> v[i];
        if(p == 0){
            root = i;
        }else{
            g[i].push_back(p);
            g[p].push_back(i);
        }
    }
    DFS(root, 0);
    cout << dp[stamp][m];
}

• Subtask 1: 100 / 100