Submission #23501

#TimeUsernameProblemLanguageResultExecution timeMemory
23501natsukagamiFireworks (APIO16_fireworks)C++14
26 / 100
0 ms4132 KiB
#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; typedef pair<int, int> ii; const int MAXN = 1e5 + 5; struct node { int total; ll off; priority_queue<ii> q; node() { total = off = 0; } } *V[MAXN]; void merge(node *&a, node *&b) { // merge a <- b if (a->q.size() < b->q.size()) swap(a, b); // small to large a->total += b->total; a->off += b->off; while (b->q.size()) { a->q.push(b->q.top()); b->q.pop(); } } void opt(node *a, int k) { // optimize with k a->off += k; int mx, mn; while (a->total > 0) { mx = mn = a->q.top().x; a->total -= a->q.top().y; a->q.pop(); } while (a->total == 0) { a->total -= a->q.top().y; mn = a->q.top().x; a->q.pop(); } // cout << "ck " << mn << ' ' << mx << endl; while (a->q.size() && a->q.top().x >= mn) { a->total -= a->q.top().y; a->q.pop(); } // raise total to -1 a->q.push(ii(mn, -1 - a->total)); // push 0 in a->q.push(ii(mn + k, 1)); // push 1 in a->q.push(ii(mx + k, 1)); // fix total a->total = 1; } int N, M; int par[MAXN], edge[MAXN], deg[MAXN]; int main() { ios_base::sync_with_stdio(false); cin >> N >> M; for (int i = 2; i <= N + M; ++i) { cin >> par[i] >> edge[i]; ++deg[par[i]]; } for (int i = 1; i <= N + M; ++i) V[i] = new node(); for (int i = N + M; i >= 1; --i) { if (!deg[i]) { // i is leaf V[i]->total = 1; V[i]->off = edge[i]; V[i]->q.push(ii(edge[i], 2)); } else { opt(V[i], edge[i]); } // cout << "v = " << i << ":" << endl; // cout << V[i]->off << ' ' << V[i]->total << endl << "qq:" << endl; // auto qq = V[i]->q; // while (qq.size()) { // cout << qq.top().x << ' ' << qq.top().y << endl; // qq.pop(); // } if (i > 1) merge(V[par[i]], V[i]); } vector<ii> P; while (V[1]->q.size()) { P.push_back(V[1]->q.top()); V[1]->total -= V[1]->q.top().y; V[1]->q.pop(); } reverse(P.begin(), P.end()); ll ans = V[1]->off, last = 0, cur = V[1]->off; for (auto i: P) { // cout << i.x << ' ' << i.y << ' ' << V[1]->total << ' ' << cur << endl; cur += (i.x - last) * V[1]->total; ans = min(ans, cur); V[1]->total += i.y; last = i.x; } cout << ans << endl; }

Compilation message (stderr)

fireworks.cpp: In function 'void opt(node*, int)':
fireworks.cpp:48:18: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  a->q.push(ii(mx + k, 1));
                  ^
fireworks.cpp:39:21: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while (a->q.size() && a->q.top().x >= mn) {
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...