| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 500849 | Stickfish | Fireworks (APIO16_fireworks) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ll = __int128;
struct dpvl {
ll l;
ll r;
ll mn;
dpvl() {}
dpvl(ll l_, ll r_, ll mn_): l(l_), r(r_), mn(mn_) {}
ll operator()(ll x) {
if (l <= x && x <= r)
return mn;
return min(abs(l - x), abs(r - x)) + mn;
}
};
const ll MAXN = 300003;
const ll INF = 1.77013e18;
vector<pair<ll, ll>> edg[MAXN];
pair<ll, ll> root[MAXN];
ll get_vl(vector<dpvl>& v, ll x) {
ll ans = 0;
for (auto d : v) {
ans += d(x);
}
return ans;
}
ll lower_bound_dir(vector<dpvl>& v, ll x) {
ll lb = -INF, ub = INF;
while (ub - lb > 1) {
ll mb = (lb + ub) / 2;
if (get_vl(v, mb + 1) - get_vl(v, mb) < x)
lb = mb;
else
ub = mb;
}
return ub;
}
dpvl dfs(ll v, ll n) {
if (v >= n) {
return {root[v].second, root[v].second, 0};
}
vector<dpvl> ch;
for (auto [u, d] : edg[v]) {
ch.push_back(dfs(u, n));
}
ll l = lower_bound_dir(ch, 0);
ll r = lower_bound_dir(ch, 1);
//assert(get_vl(ch, l) == get_vl(ch, r) && get_vl(ch, l - 1)
ll mn = 0;
for (auto d : ch)
mn += d(l);
return {l + root[v].second, r + root[v].second, mn};
}
ll input() {
long long x;
cin >> x;
return x;
}
signed main() {
ll n = input();
ll m = input();
ll addans = 0;
for (ll i = 1; i < n + m; ++i) {
ll u = input();
ll d = input();
--u;
if (u >= n) {
addans += d;
} else {
edg[u].push_back({i, d});
root[i] = {u, d};
}
}
cout << (long long)(dfs(0, n).mn + addans) << endl;
}