oj.uz

Submission #685243

# Submission time Handle Problem Language Result Execution time Memory
685243 2023-01-23T17:55:36 Z Ronin13 Biochips (IZhO12_biochips) C++14
100 / 100
 567 ms 397144 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 2e5 + 1;
vector <vector <int> > g(nmax);
int dp[nmax][501];
vector <int> a(nmax);
int ans = 0;
int last;
int m;
void dfs(int v, int e = -1){
    for(int j=  500; j >= 1; j--){
            dp[v][j] = max(dp[v][j], dp[last][j - 1] + a[v]);
            dp[v][j] = max(dp[v][j], dp[last][j]);
    }
    ans = max(ans, dp[v][m]);
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
    }
    for(int j = 500; j >= 1; j--){
        dp[v][j] = max(dp[v][j], dp[last][j]);
    }
    last = v;
}

int main(){
    int n; cin >> n;
    cin >> m;
    int root = 0;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        g[x].pb(i);
        if(!x) root = i;
        cin >> a[i];
    }
    for(int i = 1; i <= 500; i++)
        dp[0][i] = -1e9;
    dfs(root);
    cout << ans;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 29 ms 23396 KB Output is correct
5 Correct 32 ms 25528 KB Output is correct
6 Correct 32 ms 25548 KB Output is correct
7 Correct 443 ms 296208 KB Output is correct
8 Correct 433 ms 296188 KB Output is correct
9 Correct 468 ms 359912 KB Output is correct
10 Correct 567 ms 397144 KB Output is correct