oj.uz

Submission #685235

# Submission time Handle Problem Language Result Execution time Memory
685235 2023-01-23T17:49:15 Z Ronin13 Biochips (IZhO12_biochips) C++14
10 / 100
 375 ms 398540 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 m=  500; m >= 1; m--){
      dp[v][m] = max(dp[v][m], dp[last][m - 1] + a[v]);
    }
    ans = max(ans, dp[v][m]);
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
    }
    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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5716 KB Output isn't correct
2 Correct 3 ms 5716 KB Output is correct
3 Incorrect 4 ms 5972 KB Output isn't correct
4 Incorrect 24 ms 23480 KB Output isn't correct
5 Incorrect 26 ms 25556 KB Output isn't correct
6 Incorrect 25 ms 25556 KB Output isn't correct
7 Incorrect 344 ms 297492 KB Output isn't correct
8 Incorrect 338 ms 297528 KB Output isn't correct
9 Incorrect 359 ms 361116 KB Output isn't correct
10 Incorrect 375 ms 398540 KB Output isn't correct