Submission #1210024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210024		TAMREF	Fireworks (APIO16_fireworks)	C++20	100 / 100	123 ms	28212 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
int p[300005], id[300005];
ll c[300005];

priority_queue<ll> pq[300005];
ll off[300005], inc[300005]; // offset, inclination at x = 0


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    id[1] = 1;
    for(int i = 2; i <= n + m; i++) {
        cin >> p[i] >> c[i];
        id[i] = i;
    }

    for(int i = n + m; i > 1; i--) {
        int j = p[i];

        if(i > n) {
            off[id[j]] += c[i];
            --inc[id[j]];

            pq[id[j]].push(c[i]);
            pq[id[j]].push(c[i]);
        } else {
            #ifdef TAMREF
            {
                cerr << "id = " << i << "\n";
                cerr << "off = " << off[id[i]] << ", inc = " << inc[id[i]] << '\n';
                priority_queue<ll> tmp;
                while(pq[id[i]].size()) {
                    tmp.push(pq[id[i]].top());
                    cerr << pq[id[i]].top() << ' ';
                    pq[id[i]].pop();
                }
                cerr << '\n';
                pq[id[i]] = tmp;
            }
            #endif
            // update myself
            int maxinc = pq[id[i]].size() + inc[id[i]];
            #ifdef TAMREF
            cerr << "maxinc = " << maxinc << "\n";
            #endif
            while(pq[id[i]].size() && maxinc-- > 1) pq[id[i]].pop();
            
            // --inc[id[i]];
            off[id[i]] += c[i];
            ll b = pq[id[i]].top(); pq[id[i]].pop();
            ll a = pq[id[i]].top(); pq[id[i]].pop();
            pq[id[i]].push(a + c[i]);
            pq[id[i]].push(b + c[i]);

            #ifdef TAMREF
            {
                cerr << "phase 2 id = " << i << "\n";
                cerr << "off = " << off[id[i]] << ", inc = " << inc[id[i]] << '\n';
                priority_queue<ll> tmp;
                while(pq[id[i]].size()) {
                    tmp.push(pq[id[i]].top());
                    cerr << pq[id[i]].top() << ' ';
                    pq[id[i]].pop();
                }
                cerr << '\n';
                pq[id[i]] = tmp;
            }
            #endif

            if(pq[id[i]].size() > pq[id[j]].size()) swap(id[i], id[j]);

            off[id[j]] += off[id[i]];
            inc[id[j]] += inc[id[i]];
            while(pq[id[i]].size()) {
                pq[id[j]].push(pq[id[i]].top());
                pq[id[i]].pop();
            }
        }
    }
    {
        #ifdef TAMREF
        cerr << "id = " << 1 << "\n";
        cerr << "off = " << off[id[1]] << ", inc = " << inc[id[1]] << '\n';
        priority_queue<ll> tmp;
        while(pq[id[1]].size()) {
            tmp.push(pq[id[1]].top());
            cerr << pq[id[1]].top() << ' ';
            pq[id[1]].pop();
        }
        cerr << '\n';
        pq[id[1]] = tmp;
        #endif
    }

    int maxinc = pq[id[1]].size() + inc[id[1]];
    while(maxinc-- > 1) pq[id[1]].pop();

    pq[id[1]].push(0);

    {
        #ifdef TAMREF
        cerr << "phase 2 id = " << 1 << "\n";
        cerr << "off = " << off[id[1]] << ", inc = " << inc[id[1]] << '\n';
        priority_queue<ll> tmp;
        while(pq[id[1]].size()) {
            tmp.push(pq[id[1]].top());
            cerr << pq[id[1]].top() << ' ';
            pq[id[1]].pop();
        }
        cerr << '\n';
        pq[id[1]] = tmp;
        #endif
    }
    ll ans = off[id[1]], inc = 0    ;
    while(pq[id[1]].size() > 1) {
        ll x = pq[id[1]].top(); pq[id[1]].pop();
        ll y = pq[id[1]].top();

        ll dlt = (inc++) * (x-y);
        #ifdef TAMREF
        cerr << "dlt = " << dlt << ", inc = " << inc-1 << '\n';
        #endif

        ans -= dlt;
    }
    cout << ans << '\n';
}

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