Submission #970521

#	Time	Username	Problem	Language	Result	Execution time	Memory
970521		kilkuwu	Fireworks (APIO16_fireworks)	C++17	100 / 100	135 ms	44868 KiB

fireworks

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n, m;
  std::cin >> n >> m;
  std::vector<int> P(n + m), C(n + m);
  for (int i = 1; i < n + m; i++) {
    std::cin >> P[i] >> C[i];
    --P[i];
  }

  // we do dfs now 
  // f(x) is the minimum value to get 
  std::vector<int64_t> a(n + m), b(n + m);
  std::vector<std::priority_queue<int64_t>> dp(n + m);

  auto merge = [&](int i, int j) {
    a[i] += a[j];
    b[i] += b[j];
    if (dp[i].size() < dp[j].size()) {
      std::swap(dp[i], dp[j]);
    }
    while (dp[j].size()) {
      dp[i].push(dp[j].top());
      dp[j].pop();
    }
  };

  for (int i = n + m - 1; i >= n; i--) {
    a[i] = 1;
    b[i] = -C[i];
    dp[i].push(C[i]);
    dp[i].push(C[i]);
    merge(P[i], i);
  }
  dbg("done peasants");

  auto pop_right = [&](int i) -> int64_t {
    int64_t popped = dp[i].top();
    int64_t v = a[i] * popped + b[i];
    --a[i];
    b[i] = v - a[i] * popped;
    dp[i].pop();
    return popped;
  };

  auto insert_right = [&](int i, int64_t p) -> void {
    int64_t v = a[i] * p + b[i];
    a[i]++;
    b[i] = v - a[i] * p;
    dp[i].push(p);
  };

  for (int i = n - 1; i > 0; i--) {
    while (a[i] > 1) {
      pop_right(i);
    }
    auto t1 = pop_right(i) + C[i];
    auto t0 = pop_right(i) + C[i]; 
    insert_right(i, t0);
    insert_right(i, t1);
    b[i] += C[i];
    merge(P[i], i);
  }

  while (a[0] > 0) {
    pop_right(0);
  }

  std::cout << a[0] * dp[0].top() + b[0] << nl;
}

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