# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1210023 | TAMREF | Fireworks (APIO16_fireworks) | C11 | 0 ms | 0 KiB |
#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';
}