Submission #443798

#	Time	Username	Problem	Language	Result	Execution time	Memory
443798		JovanB	Biochips (IZhO12_biochips)	C++17	100 / 100	657 ms	414940 KiB

biochips

#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 / 100