Submission #1261862

#TimeUsernameProblemLanguageResultExecution timeMemory
1261862ngmtuanFireworks (APIO16_fireworks)C++20
100 / 100
216 ms150548 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define sz(x) ((int)(x).size()) #define all(x) ((x).begin(), (x).end()) const int N = 3e5 + 5; int n, m; int p[N], c[N]; vector<int> g[N]; struct slopes { ll a, b; priority_queue<ll> l; multiset<ll> r; slopes() { a = -1, b = 0; l.push(0); r.insert(0); } }; slopes dfs(int u) { if (g[u].empty()) { return slopes(); } slopes h; h.a = h.b = 0; h.l.pop(), h.r.clear(); for (int v : g[u]) { auto f = dfs(v); assert(f.a + f.l.size() == 0); while (f.r.size() > 1) f.r.erase(f.r.find(*f.r.rbegin())); vector<ll> vec; for (auto x : f.r) vec.push_back(x + c[v]); f.r.clear(); for (ll i : vec) f.r.insert(i); ll tmp = f.l.top(); f.l.pop(), f.l.push(tmp + c[v]); f.b += c[v]; if (h.l.size() + h.r.size() < f.l.size() + f.r.size()) swap(h, f); while (f.l.size()) { h.l.push(f.l.top()); f.l.pop(); } for (auto x : f.r) { h.r.insert(x); } h.a += f.a, h.b += f.b; while (!h.l.empty() && !h.r.empty() && h.l.top() > *h.r.begin()) { h.r.insert(h.l.top()); h.l.pop(); h.l.push(*h.r.begin()); h.r.erase(h.r.begin()); } } return h; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 2; i <= n + m; i++) { cin >> p[i] >> c[i]; g[p[i]].push_back(i); } auto res = dfs(1); while (res.l.size()) { res.b -= res.l.top(); res.l.pop(); } cout << res.b << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...