oj.uz

Submission #834685

# Submission time Handle Problem Language Result Execution time Memory
834685 2023-08-22T17:06:36 Z FEDIKUS Fireworks (APIO16_fireworks) C++17
0 / 100
 10 ms 21460 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21376 KB Output is correct
2 Correct 9 ms 21332 KB Output is correct
3 Incorrect 9 ms 21460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Incorrect 10 ms 21332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21376 KB Output is correct
2 Correct 9 ms 21332 KB Output is correct
3 Incorrect 9 ms 21460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21376 KB Output is correct
2 Correct 9 ms 21332 KB Output is correct
3 Incorrect 9 ms 21460 KB Output isn't correct
4 Halted 0 ms 0 KB -