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 <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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |