oj.uz

Submission #443798

# Submission time Handle Problem Language Result Execution time Memory
443798 2021-07-12T06:25:40 Z JovanB Biochips (IZhO12_biochips) C++17
100 / 100
 657 ms 414940 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 6 ms 9724 KB Output is correct
2 Correct 6 ms 9724 KB Output is correct
3 Correct 6 ms 9932 KB Output is correct
4 Correct 19 ms 27724 KB Output is correct
5 Correct 22 ms 29956 KB Output is correct
6 Correct 24 ms 29988 KB Output is correct
7 Correct 418 ms 310636 KB Output is correct
8 Correct 395 ms 310552 KB Output is correct
9 Correct 578 ms 376364 KB Output is correct
10 Correct 657 ms 414940 KB Output is correct