Submission #1086464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086464		vjudge1	Fireworks (APIO16_fireworks)	C++17	100 / 100	203 ms	102724 KiB

fireworks

#include <iostream>
#include <map>
#include <utility>
#include <vector>

struct ConvexLinearSet {
  int m = 0;
  long long c = 0;
  std::map<long long, int> m_changes; // key: xpos, val: dm

  int size() {
    return m_changes.size();
  }
  
  void merge_with(const ConvexLinearSet& o) {
    m += o.m;
    c += o.c;
    for (auto [x, dm]: o.m_changes) {
      m_changes[x] += dm;
    }
  }

  long long query_min() {
    long long x;
    int dm;
    auto it = m_changes.rbegin();
    while (it != m_changes.rend() && m >= 0) {
      std::tie(x, dm) = *it;

      // update current m & c
      // m*x + c = (m - dm)*x + new_c -> new_c = x*dm + c
      m -= dm;
      c += x * dm;
      it++;
    }

    return x * m + c;
  }

  void apply_w(int w) {
    long long x, x_prev, xprev2;
    int dm;
    while (!m_changes.empty() && m >= 0) {
      // pop largest
      x_prev = x;
      std::tie(x, dm) = *m_changes.rbegin();
      m_changes.erase(x);

      // update current m & c
      // m*x + c = (m - dm)*x + new_c -> new_c = x*dm + c
      m -= dm;
      c += x * dm;
    }

    bool has_zero_grad = (m == -dm);
    long long minval = x * m + c;
    // std::cerr << "minimum at m=" << m << " x=" << x << " val=" << minval << std::endl;

    if (m != -1) {
      m_changes[x] -= m + 1;
    }

    m_changes[x + w]++; // make next grad = 0 here

    // we are at m = 0 now, let's jump to the end of m = 0
    x = has_zero_grad ? x_prev : x;
    x += w;

    // make next_m = 1
    // const = x + new_c -> new_c = const - x
    m_changes[x]++;
    m = 1;
    c = minval - x;
  }

  void debug() {
    std::cerr << "{\n";
    int cur_m = m;
    long long cur_c = c;
    for (auto it = m_changes.rbegin(); it != m_changes.rend(); it++) {
      long long x;
      int dm;
      std::tie(x, dm) = *it;
      std::cerr << "  y = (" << cur_m << ")x + (" << cur_c << ") from x >= " << x << '\n';
      cur_m -= dm;
      cur_c += x * dm;
    }
    std::cerr << "  y = (" << cur_m << ")x + (" << cur_c << ") otherwise\n";
    std::cerr << "}\n";

    std::cerr << "changes:"; for (auto [x, dm]: m_changes) std::cerr << " (x=" << x << ",d=" << dm << ")"; std::cerr << std::endl;
  }
};

int main() {
  std::cin.tie(NULL)->sync_with_stdio(false);

  int n, m;
  std::cin >> n >> m;

  std::vector<ConvexLinearSet> sets(n + m + 1);
  std::vector<std::vector<int>> adj(n + m + 1);
  std::vector<int> w(n + m + 1);
  w[1] = 0;
  for (int i = 2; i <= n + m; i++) {
    int par;
    std::cin >> par >> w[i];

    adj[par].push_back(i);
    if (i > n) {
      // leaf nodes
      sets[i].m = 1;
      sets[i].c = -w[i];
      sets[i].m_changes[w[i]] = 2;
    }
  }

  auto dfs = [&](auto &&dfs_fn, int u) -> void {
    if (adj[u].empty()) {
      // base case
      // std::cerr << "node=" << u << " w=" << w[u] << " ";
      // sets[u].debug();
      // std::cerr << std::endl;
      return;
    }

    // recursive + find largest set
    for (int v: adj[u]) {
      dfs_fn(dfs_fn, v);
      if (sets[u].size() < sets[v].size()) {
        std::swap(sets[u], sets[v]);
      }
    }

    // merge sets
    for (int v: adj[u]) {
      sets[u].merge_with(sets[v]);
    }

    sets[u].apply_w(w[u]);

    // std::cerr << "node=" << u << " w=" << w[u] << " ";
    // sets[u].debug();
    // std::cerr << std::endl;
  };

  dfs(dfs, 1);

  std::cout << sets[1].query_min() << std::endl;

  return 0;
}

Compilation message (stderr)

fireworks.cpp: In member function 'void ConvexLinearSet::apply_w(int)':
fireworks.cpp:41:26: warning: unused variable 'xprev2' [-Wunused-variable]
   41 |     long long x, x_prev, xprev2;
      |                          ^~~~~~
fireworks.cpp:45:14: warning: 'x' is used uninitialized in this function [-Wuninitialized]
   45 |       x_prev = x;
      |       ~~~~~~~^~~
fireworks.cpp:55:32: warning: 'dm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     bool has_zero_grad = (m == -dm);
      |                                ^~~
fireworks.cpp:67:7: warning: 'x_prev' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     x += w;
      |     ~~^~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:37:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |     return x * m + c;
      |            ~~^~~
fireworks.cpp:24:15: note: 'x' was declared here
   24 |     long long x;
      |               ^

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