Submission #226709

#	Time	Username	Problem	Language	Result	Execution time	Memory
226709		natsukagami	Fireworks (APIO16_fireworks)	C++17	100 / 100	231 ms	48856 KiB

fireworks

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, int> ii;
const int MAXN = 3e5 + 5;
struct node {
  int total;
  ll off;
  priority_queue<ii> q;
  node() { total = off = 0; }
  node(node &&v) noexcept : total(v.total), off(v.off), q(std::move(v.q)) {}
  node &operator=(node &&v) {
    total = v.total;
    off = v.off;
    q = std::move(v.q);
    return *this;
  }
} 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;
  ll 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];
// random_device rd;
int main() {
  ios_base::sync_with_stdio(false);
  // N = M = 1e5;
  cin >> N >> M;
  for (int i = 2; i <= N + M; ++i) {
    // par[i] = rd()%(i-1) + 1;
    // edge[i] = rd()%int(1e9) + 1;
    cin >> par[i] >> edge[i];
    ++deg[par[i]];
  }
  for (int i = N + M; i >= 1; --i) {
    // cout << i << endl;
    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:21: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   while (a.q.size() && a.q.top().x >= mn) {
          ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fireworks.cpp:57:18: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   a.q.push(ii(mx + k, 1));
               ~~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45