Submission #257458

#	Time	Username	Problem	Language	Result	Execution time	Memory
257458		EntityIT	Fireworks (APIO16_fireworks)	C++14	100 / 100	212 ms	51176 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

struct Function {
  int64_t a, b;
  priority_queue<int64_t>* slope_changing_points;
  Function()
      : a(0),
        b(0),
        slope_changing_points(new priority_queue<int64_t>()) {}

  Function& operator+=(Function& o) {
    a += o.a;
    b += o.b;

    if (slope_changing_points->size() < o.slope_changing_points->size()) {
      swap(slope_changing_points, o.slope_changing_points);
    }
    while (o.slope_changing_points->size()) {
      slope_changing_points->emplace(o.slope_changing_points->top());
      o.slope_changing_points->pop();
    }

    return *this;
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n_junctions, n_explosives; cin >> n_junctions >> n_explosives;
  vec<int, 1> parents(n_junctions + n_explosives, -1), parent_edges(n_junctions + n_explosives);
  for (int i = 1; i < n_junctions + n_explosives; ++i) {
    cin >> parents[i] >> parent_edges[i]; --parents[i];
  }

  vec<Function, 1> functions(n_junctions + n_explosives);
  for (int i = n_junctions; i < n_junctions + n_explosives; ++i) {
    functions[i].a = 1;
    functions[i].b = -parent_edges[i];
    functions[i].slope_changing_points->emplace(parent_edges[i]);
    functions[i].slope_changing_points->emplace(parent_edges[i]);
    functions[parents[i]] += functions[i];
  }

  for (int i = n_junctions - 1; i; --i) {
    while (functions[i].a > 1) {
      --functions[i].a;
      functions[i].b += functions[i].slope_changing_points->top();
      functions[i].slope_changing_points->pop();
    }

    functions[i].b -= parent_edges[i];
    auto tmp_1 = functions[i].slope_changing_points->top(); functions[i].slope_changing_points->pop();
    auto tmp_2 = functions[i].slope_changing_points->top(); functions[i].slope_changing_points->pop();
    functions[i].slope_changing_points->emplace(tmp_1 + parent_edges[i]);
    functions[i].slope_changing_points->emplace(tmp_2 + parent_edges[i]);
    functions[parents[i]] += functions[i];
  }

  while (functions[0].a) {
    --functions[0].a;
    functions[0].b += functions[0].slope_changing_points->top();
    functions[0].slope_changing_points->pop();
  }

  cout << functions[0].b << '\n';

  return 0;
}

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