Submission #1194301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194301		ackhava	Fireworks (APIO16_fireworks)	C++20	7 / 100	3 ms	4936 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){
    return max(max(f.fi+f.se.fi-x,f.fi+x-f.se.se),f.fi);
}

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);
    for(auto i:child[node])dp[node].fi -= getval(dp[i],dp[node].se.se);
    assert(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