Submission #1185050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185050		byunjaewoo	Fireworks (APIO16_fireworks)	C++20	100 / 100	142 ms	37244 KiB

fireworks

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=300010;
int n, m, t, ans, p[N], c[N], a[N];
priority_queue<int> pq[N];

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin>>n>>m;
    for (int i=2; i<=n+m; i++) cin>>p[i]>>a[i], ans+=a[i], c[p[i]]++;
    for (int i=n+m; i>=1; i--) {
        if (i>n) pq[i].push(a[i]), pq[i].push(a[i]);
        else {
            for (int j=1; j<c[i]; j++) pq[i].pop();
            int x=pq[i].top()+a[i]; pq[i].pop();
            int y=pq[i].top()+a[i]; pq[i].pop();
            pq[i].push(x), pq[i].push(y);
        }
        if (i==1) break;
        if (pq[p[i]].size()<pq[i].size()) swap(pq[p[i]], pq[i]);
        while (!pq[i].empty()) pq[p[i]].push(pq[i].top()), pq[i].pop();
    }
    while (pq[1].size()>1) {
        int v=pq[1].top(); pq[1].pop(), v-=pq[1].top();
        ans-=v*(t++);
    }
    cout<<ans-pq[1].top()*(t++);
    return 0;
}

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