Submission #101848

#TimeUsernameProblemLanguageResultExecution timeMemory
101848cerberusFireworks (APIO16_fireworks)C++17
7 / 100
11 ms7552 KiB
/* cerberus97 - Hanit Banga */ #include <iostream> #include <iomanip> #include <cassert> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <algorithm> using namespace std; #define pb push_back #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL) typedef long long ll; typedef long double ld; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const int N = 3e5 + 10; int p[N]; ll c[N], val[N]; vector<int> g[N]; pair<ll, pll> solve(int u); int main() { fast_cin(); int n, m; cin >> n >> m; n += m; for (int i = 2; i <= n; ++i) { cin >> p[i] >> c[i]; val[i] = val[p[i]] + c[i]; g[p[i]].pb(i); } auto ans = solve(1); cout << ans.first << endl; } pair<ll, pll> solve(int u) { if (g[u].empty()) { return {0, {val[u], val[u]}}; } ll base = 0, cur = 0; vector<pll> intervals; for (auto &v : g[u]) { auto i = solve(v); base += i.first; intervals.push_back({i.second.first, 1}); intervals.push_back({i.second.second, -1}); cur += i.second.first; } ll best = cur; pll best_interval = {0, 0}; int lo = 0, hi = intervals.size() / 2; sort(intervals.begin(), intervals.end()); ll cand = 0; for (auto &i : intervals) { if (cand < i.first) { cur += (i.first - cand) * (lo - hi); cand = i.first; if (cur < best) { best = cur; best_interval = {cand, cand}; } else if (cur == best) { best_interval.second = cand; } } if (i.second == 1) { --hi; } else { ++lo; } } best += base; // cout << u << ' ' << best << ' ' << best_interval.first << ' ' << best_interval.second << endl; return {best, best_interval}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...