oj.uz

Submission #320138

# Submission time Handle Problem Language Result Execution time Memory
320138 2020-11-07T18:32:31 Z jovan_b Biochips (IZhO12_biochips) C++17
100 / 100
 587 ms 415076 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

int val[200005];
int par[200005];
vector <int> graf[200005];

int tajm;

int in[200005];
int out[200005];
int niz[200005];
int dp[200005][505];

void dfs(int v){
    in[v] = ++tajm;
    for(auto c : graf[v]) dfs(c);
    out[v] = tajm;
}

vector <pair <int, int>> vec[200005];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    vector <int> roots;
    for(int i=1; i<=n; i++){
        cin >> par[i] >> val[i];
        if(par[i]) graf[par[i]].push_back(i);
        else roots.push_back(i);
    }
    for(auto c : roots) dfs(c);
    for(int i=1; i<=n; i++){
        //cout << in[i] << " " << out[i] << " " << val[i] << endl;
        vec[out[i]].push_back({in[i]-1, val[i]});
    }
    for(int i=0; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j] = -1000000000;
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j] = dp[i-1][j];
            for(auto c : vec[i]){
                dp[i][j] = max(dp[i][j], dp[c.first][j-1] + c.second);
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9832 KB Output is correct
2 Correct 7 ms 9984 KB Output is correct
3 Correct 7 ms 9964 KB Output is correct
4 Correct 24 ms 28032 KB Output is correct
5 Correct 23 ms 30060 KB Output is correct
6 Correct 24 ms 30060 KB Output is correct
7 Correct 373 ms 310884 KB Output is correct
8 Correct 410 ms 310628 KB Output is correct
9 Correct 513 ms 376344 KB Output is correct
10 Correct 587 ms 415076 KB Output is correct