Submission #834685

#	Time	Username	Problem	Language	Result	Execution time	Memory
834685		FEDIKUS	Fireworks (APIO16_fireworks)	C++17	0 / 100	10 ms	21460 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll,ll>;

const ll maxn=3e5+10;

vector<pii> g[maxn];
ll popravka[maxn];
multiset<ll> slope[maxn];

void dfs(ll node,ll c=-1){
    for(auto i:g[node]){
        dfs(i.first,i.second);
    }
    pair<ll,ll> maxi={-1,-1};
    for(auto i:g[node]){
        maxi=max(maxi,{ll(slope[i.first].size()),i.first});
    }
    if(maxi.first!=-1){
        swap(slope[maxi.second],slope[node]);
        popravka[node]=popravka[maxi.second];
        for(auto i:g[node]){
            if(i.first==maxi.second) continue;
            for(ll j:slope[i.first]){
                slope[node].emplace(popravka[i.first]-popravka[node]+j);
            }
            auto it=slope[node].end();
            it--;
            slope[node].erase(it);
        }
    }
    if(slope[node].empty()){
        slope[node].emplace(c);
        slope[node].emplace(c);
        return;
    }

    if(c!=-1){
        popravka[node]-=c;
        popravka[node]+=c;
        auto it=--slope[node].end();
        ll posl=*it+c;
        slope[node].erase(it);
        it=--slope[node].end();
        ll predposl=*it+c;
        slope[node].erase(it);
        slope[node].emplace(posl);
        slope[node].emplace(predposl);
    }
    while(!slope[node].empty() && *slope[node].begin()+popravka[node]<=0){
        slope[node].erase(slope[node].begin());
    }

}

int main(){
    ll n,m;
    cin>>n>>m;
    n+=m;
    ll vr=0;
    for(ll i=2;i<=n;i++){
        ll p,c; cin>>p>>c;
        g[p].push_back({i,c});
        vr+=c;
    }
    dfs(1);
    ll sl=0;
    vector<ll> nes;
    for(ll i:slope[1]) nes.push_back(i+popravka[1]);
    reverse(nes.begin(),nes.end());
    nes.push_back(0);
    for(ll i=1;i<ll(nes.size());i++){
        vr-=sl*(nes[i-1]-nes[i]);
        sl++;
    }
    cout<<vr;
    return 0;
}

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