Submission #834683

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

fireworks

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int,int>;

const int maxn=3e5+10;

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

void dfs(int node,int c=-1){
    for(auto i:g[node]){
        dfs(i.first,i.second);
    }
    pair<int,int> maxi={-1,-1};
    for(auto i:g[node]){
        maxi=max(maxi,{int(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(int 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();
        int posl=*it+c;
        slope[node].erase(it);
        it=--slope[node].end();
        int 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(){
    int n,m;
    cin>>n>>m;
    n+=m;
    int vr=0;
    for(int i=2;i<=n;i++){
        int p,c; cin>>p>>c;
        g[p].push_back({i,c});
        vr+=c;
    }
    dfs(1);
    int sl=0;
    vector<int> nes;
    for(int i:slope[1]) nes.push_back(i+popravka[1]);
    reverse(nes.begin(),nes.end());
    nes.push_back(0);
    for(int i=1;i<int(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