Submission #834763

#	Time	Username	Problem	Language	Result	Execution time	Memory
834763		FEDIKUS	Fireworks (APIO16_fireworks)	C++17	100 / 100	423 ms	105052 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];
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]);
        for(auto i:g[node]){
            if(i.first==maxi.second) continue;
            for(ll j:slope[i.first]){
                slope[node].emplace(j);
            }
        }
    }
    for(int i=0;i<ll(g[node].size())-1;i++){
        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){
        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);
    }

}

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);
    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: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45