oj.uz

Submission #834687

# Submission time Handle Problem Language Result Execution time Memory
834687 2023-08-22T17:10:21 Z FEDIKUS Fireworks (APIO16_fireworks) C++17
0 / 100
 11 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];
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);
            }
            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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21364 KB Output is correct
2 Correct 10 ms 21428 KB Output is correct
3 Incorrect 10 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 21328 KB Output is correct
2 Correct 9 ms 21364 KB Output is correct
3 Incorrect 11 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 11 ms 21364 KB Output is correct
2 Correct 10 ms 21428 KB Output is correct
3 Incorrect 10 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 11 ms 21364 KB Output is correct
2 Correct 10 ms 21428 KB Output is correct
3 Incorrect 10 ms 21460 KB Output isn't correct
4 Halted 0 ms 0 KB -