Submission #1194291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194291		ackhava	Fireworks (APIO16_fireworks)	C++20	7 / 100	3 ms	5004 KiB

fireworks

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define REP(i,o,n) for(auto i=o;i<n;i++)
using namespace std;

pair<long long,pair<long long,long long>> dp[200100];

long long getval(pair<long long,pair<long long,long long>> f, long long x){
    if(f.se.se < x)return x+f.fi-f.se.se;
    if(f.se.fi < x)return f.fi;
    return f.se.fi+f.fi-x;
}

vector<long long> child[200100];
long long par[200100];

void dfs(long long node){
    if(!child[node].size()){
        dp[node]={0,{par[node],par[node]}};
        return;
    }
    vector<long long> v;
    for(auto i:child[node])dfs(i),v.pb(dp[i].se.fi),v.pb(dp[i].se.se);
    sort(v.begin(),v.end());
    dp[node].se = {v[child[node].size()-1],v[child[node].size()]};
    dp[node].fi = 0;
    for(auto i:child[node])dp[node].fi += getval(dp[i],dp[node].se.fi);
    dp[node].se.fi += par[node];
    dp[node].se.se += par[node];
}

signed main() {
    long long n,m;cin>>n>>m;
    REP(i,2,n+m+1){
        long long p;cin>>p;
        cin>>par[i];
        child[p].pb(i);
    }
    dfs(1);
    cout<<dp[1].fi;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45