Submission #419522

#	Time	Username	Problem	Language	Result	Execution time	Memory
419522		ansol4328	Fireworks (APIO16_fireworks)	C++14	100 / 100	325 ms	72500 KiB

fireworks

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

int N, M, C[300005];
vector<int> lst[300005];
P par[300005];
priority_queue<ll,vector<ll>,greater<ll>> inc[300005];
priority_queue<ll> Dec[300005];
ll minv[300005];

void combine(int v, int v1)
{
    ll val=par[v1].se;
    if(!Dec[v].empty()){
        val+=Dec[v].top(); Dec[v].pop();
    }
    Dec[v].push(val); val=par[v1].se;
    if(!inc[v].empty()) val+=inc[v].top();
    while(!inc[v].empty()) inc[v].pop();
    inc[v].push(val);
}

void move(int cur, int v)
{
    while(!inc[v].empty()){
        inc[cur].push(inc[v].top());
        inc[v].pop();
    }
    while(!Dec[v].empty()){
        Dec[cur].push(Dec[v].top());
        Dec[v].pop();
    }
    while(!Dec[cur].empty() && !inc[cur].empty() && Dec[cur].top()>inc[cur].top()){
        ll d=Dec[cur].top();
        ll i=inc[cur].top();
        Dec[cur].pop(); inc[cur].pop();
        Dec[cur].push(i); inc[cur].push(d);
    }
}

void add(int cur, int v)
{
    vector<ll> tmp;
    if(inc[v].top()<Dec[cur].top()){
        ll mv=minv[v]+minv[cur], x=Dec[cur].top();
        //calculate mv by pq
        priority_queue<ll,vector<ll>,greater<ll>> pq(inc[v]);
        while(!pq.empty() && pq.top()<x){
            mv+=x-pq.top(); pq.pop();
        }
        move(cur,v);
        if(x>inc[cur].top()){
            while(!inc[cur].empty() && inc[cur].top()<x){
                tmp.pb(inc[cur].top());
                mv-=x-inc[cur].top();
                inc[cur].pop();
            }
            for(ll x : tmp) inc[cur].push(x);
        }
        minv[cur]=mv;
    }
    else if(inc[cur].top()<Dec[v].top()){
        ll mv=minv[v]+minv[cur], x=inc[cur].top();
        priority_queue<ll> pq(Dec[v]);
        while(!pq.empty() && pq.top()>x){
            mv+=pq.top()-x; pq.pop();
        }
        move(cur,v);
        if(x<Dec[cur].top()){
            while(!Dec[cur].empty() && Dec[cur].top()>x){
                tmp.pb(Dec[cur].top());
                mv-=Dec[cur].top()-x;
                Dec[cur].pop();
            }
            for(ll x : tmp) Dec[cur].push(x);
        }
        minv[cur]=mv;
    }
    else{
        move(cur,v); minv[cur]+=minv[v];
    }
}

int main()
{
    scanf("%d %d",&N,&M);
    for(int i=2 ; i<=N+M ; i++){
        scanf("%lld %lld",&par[i].fi,&par[i].se);
        lst[par[i].fi].pb(i);
        if(i>N) C[i]=i;
    }
    for(int i=N ; i>=1 ; i--){
        int cur=lst[i][0], v;
        combine(C[cur],cur); cur=C[cur];
        for(int j=1 ; j<lst[i].size() ; j++){
            v=lst[i][j];
            combine(C[v],v); v=C[v];
            int sz1=inc[cur].size()+Dec[cur].size();
            int sz2=inc[v].size()+Dec[v].size();
            if(sz1<sz2) swap(cur,v);
            add(cur,v);
        }
        C[i]=cur;
    }
    printf("%lld",minv[C[1]]);
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:101:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int j=1 ; j<lst[i].size() ; j++){
      |                       ~^~~~~~~~~~~~~~
fireworks.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
fireworks.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%lld %lld",&par[i].fi,&par[i].se);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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