Submission #836968

#	Time	Username	Problem	Language	Result	Execution time	Memory
836968		urieg	Fireworks (APIO16_fireworks)	C++17	100 / 100	217 ms	96368 KiB

fireworks

#include<bits/stdc++.h>
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define ve vector
typedef long long ll;
using namespace std;

const int N = 350000;
priority_queue<ll> ql[N];
priority_queue<ll, vector<ll>, greater<ll>> qr[N];
unsigned long long ans=0;
vector<pair<int, ll>> g[N];

void add(ll val, int& i, int x){
    if(ql[i].top()<val && val < qr[i].top()){
        if(x<0){
            ql[i].push(val);
        }
        else{
            qr[i].push(val);
        }
    }
    else if(ql[i].top()>=val){
        if(x>0){
            ans += ql[i].top()-val;
            qr[i].push(ql[i].top());
            ql[i].pop();
        }
        ql[i].push(val);
    }
    else if(qr[i].top()<=val){
        if(x<0){
            ans += val-qr[i].top();
            ql[i].push(qr[i].top());
            qr[i].pop();
        }
        qr[i].push(val);
    }
}

void unite(int v, int u){
    bool sw = 0;
    if(ql[u].size()+qr[u].size() > ql[v].size()+qr[v].size()){swap(v, u); sw=1;}

    while(!ql[u].empty()){
        add(ql[u].top(), v, -1);
        ql[u].pop();
    }
    while(!qr[u].empty()){
        add(qr[u].top(), v, 1);
        qr[u].pop();
    }
    if(sw){
        ql[v].swap(ql[u]);
        qr[v].swap(qr[u]);
    }
}

void dfs(int v){
    for(int i = 0;i<g[v].size();i++){
        int son = g[v][i].first;
        ll w = g[v][i].second;
        dfs(son);
        if(!g[son].size()){
            ql[son].push(w);
            qr[son].push(w);
        }
        else{
            ll l = ql[son].top(), r = qr[son].top();
            ql[son].pop();
            ql[son].push(l+w);
            while(!qr[son].empty())qr[son].pop();
            qr[son].push(r+w);
        }
        unite(v, son);
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, m;
    cin>>n>>m;
    for(int i = 1; i<n+m;i++){
        int an;ll c;
        cin>>an>>c;an--;
        g[an].push_back({i, c});
    }
    dfs(0);
    cout<<ans<<'\n';


    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0;i<g[v].size();i++){
      |                   ~^~~~~~~~~~~~

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