Submission #1253319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253319		magic_trip	Fireworks (APIO16_fireworks)	C++20	100 / 100	224 ms	94536 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> PP;
const ll Lnf = 2e18;
ll n, m;
ll num[303030];
vector<array<ll,2>> adj[303030];
priority_queue<ll> pq[303030];  //delta
void dfs(ll x){
    for(auto [next,w] : adj[x]){
        dfs(next);
        auto &pq1 = pq[num[x]]; auto &pq2 = pq[num[next]];
        if(!sz(pq2)){
            pq2.push(w); pq2.push(w);
        }
        else{
            ll b = pq2.top(); pq2.pop();
            ll a = pq2.top(); pq2.pop();
            pq2.push(a+w); pq2.push(b+w);
        }
        if(sz(pq1) < sz(pq2)){
            swap(num[x],num[next]);
            while(sz(pq1)){
                pq2.push(pq1.top()); pq1.pop();
            }
        }
        else{
            while(sz(pq2)){
                pq1.push(pq2.top()); pq2.pop();
            }
        }
//        cout<<sz(pq1)<<" "<<sz(pq2)<<endl;
    }
    for(int i = 1 ; i < sz(adj[x]) ; i++)pq[num[x]].pop();
}
int main(){
    fast;
    cin>>n>>m; n+=m;
    for(int i = 1 ; i <= n ; i++)num[i]=i;
    ll ans=0;
    for(int i = 2 ; i <= n ; i++){
        ll p,x; cin>>p>>x; adj[p].push_back({i,x}); ans+=x;
    }
    dfs(1);
    vector<ll> v;
    while(sz(pq[num[1]]))v.push_back(pq[num[1]].top()), pq[num[1]].pop();
    reverse(all(v));
    for(int i = 0, j = -sz(v)+1 ; i < sz(v) ; i++, j++)ans += (v[i]-(i?v[i-1]:0))*j;
    cout<<ans;
}

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