Submission #952880

#	Time	Username	Problem	Language	Result	Execution time	Memory
952880		ttamx	Fireworks (APIO16_fireworks)	C++17	7 / 100	33 ms	68952 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=6e5+5;

int n,m;
vector<pair<int,int>> adj[N];
int sz[N],hv[N];

struct SlopeTirck{
    int sz;
    ll lz,mn;
    priority_queue<ll> pl;
    priority_queue<ll,vector<ll>,greater<ll>> pr;
    SlopeTirck():lz(0),mn(0),pl(),pr(){}
    void insertpoint(ll x){
        if(pl.empty()||x<=pl.top()+lz){
            pl.emplace(x-lz);
        }else{
            pr.emplace(x-lz);
        }
        if(pl.size()>pr.size()){
            pr.emplace(pl.top());
            pl.pop();
        }else if(pl.size()<pr.size()){
            pl.emplace(pr.top());
            pr.pop();
        }
        sz++;
    }
    void insert(ll x){
        if(!pl.empty())mn+=max(pl.top()+lz-x,0LL);
        if(!pr.empty())mn+=max(x-pr.top()-lz,0LL);
        insertpoint(x);
        insertpoint(x);
    }
    void merge(SlopeTirck &o){
        if(!pl.empty()&&!o.pr.empty())mn+=max(pl.top()+lz-o.pr.top()-o.lz,0LL);
        if(!pr.empty()&&!o.pl.empty())mn+=max(o.pl.top()+o.lz-pr.top()-lz,0LL);
        while(!o.pl.empty()){
            insertpoint(o.pl.top()+o.lz);
            o.pl.pop();
        }
        while(!o.pr.empty()){
            insertpoint(o.pr.top()+o.lz);
            o.pr.pop();
        }
        mn+=o.mn;
    }
    void shift(ll x){
        lz+=x;
    }
    void shrink(){
        ll l=pl.top(),r=pr.top();
        while(!pl.empty())pl.pop();
        while(!pr.empty())pr.pop();
        pl.emplace(l),pr.emplace(r);
    }
}dp[N];

void dfs(int u){
    for(auto [v,w]:adj[u]){
        dfs(v);
        dp[v].shift(w);
        if(dp[v].sz>dp[u].sz)swap(dp[u],dp[v]);
        dp[u].merge(dp[v]);
    }
    dp[u].shrink();
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=2;i<=n+m;i++){
        int p,c;
        cin >> p >> c;
        adj[p].emplace_back(i,c);
    }
    for(int i=1;i<=m;i++)dp[n+i].insert(0);
    dfs(1);
    cout << dp[1].mn;
}

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