oj.uz

Submission #659571

# Submission time Handle Problem Language Result Execution time Memory
659571 2022-11-18T14:46:24 Z Vladth11 Biochips (IZhO12_biochips) C++14
100 / 100
 345 ms 405560 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 5160 KB Output is correct
4 Correct 14 ms 22868 KB Output is correct
5 Correct 14 ms 25120 KB Output is correct
6 Correct 16 ms 25140 KB Output is correct
7 Correct 253 ms 302428 KB Output is correct
8 Correct 247 ms 302484 KB Output is correct
9 Correct 332 ms 367356 KB Output is correct
10 Correct 345 ms 405560 KB Output is correct