Submission #471815

#	Time	Username	Problem	Language	Result	Execution time	Memory
471815		wleung_bvg	Harbingers (CEOI09_harbingers)	C++17	100 / 100	132 ms	31344 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
template <class C> constexpr int sz(const C &c) { return int(c.size()); }
constexpr const char nl = '\n', sp = ' '; using uint = unsigned int;
using ll = long long; using ull = unsigned long long; using ld = long double;
#if __SIZEOF_INT128__
  using i128 = __int128_t; using ui128 = __uint128_t;
#endif

const bool FIRST = true, LAST = false;
template <const bool ISFIRST, class T, class F> T bsearch(T lo, T hi, F f) {
  static_assert(is_integral<T>::value, "T must be integral");
  hi--; while (lo <= hi) {
    T mid = lo + (hi - lo) / 2;
    if (f(mid) == ISFIRST) hi = mid - 1;
    else lo = mid + 1;
  }
  return ISFIRST ? lo : hi;
}

template <class T, class Cmp = less<T>> struct ConvexHullTrickUndo {
  struct Line {
    T m, b; Line(T m = T(), T b = T()) : m(m), b(b) {}
    T eval(T x) const { return m * x + b; }
  };
  vector<pair<int, Line>> history; vector<Line> L; int back;
  ConvexHullTrickUndo() : back(0) {}
  int size() const { return back; }
  void addLine(T m, T b) {
    int i = back; if (i >= 1)
      i = bsearch<LAST>(1, i + 1, [&] (int j) {
        return Cmp()(m, L[j - 1].m) || Cmp()(L[j - 1].m, m)
            || Cmp()(b, L[j - 1].b);
      });
    if (i >= 2)
      i = bsearch<LAST>(2, i + 1, [&] (int j) {
        T c1 = (L[j - 1].m - m) * (L[j - 2].b - b);
        T c2 = (L[j - 1].b - b) * (L[j - 2].m - m);
        return c1 > c2;
      });
    if (i == int(L.size())) L.emplace_back();
    history.emplace_back(back, L[i]); L[i] = Line(m, b); back = i + 1;
  }
  void undo() { tie(back, L[back - 1]) = history.back(); history.pop_back(); }
  T getMax(T x) const {
    return L[bsearch<FIRST>(0, back - 1, [&] (int i) {
      return Cmp()(L[i + 1].eval(x), L[i].eval(x));
    })].eval(x);
  }
  void reserve(int N) { L.reserve(N); history.reserve(N); }
};

template <class T> struct StaticWeightedGraph {
  vector<int> ST, TO, A, B; vector<T> C, WEIGHT;
  StaticWeightedGraph(int V) : ST(V + 1, 0) {}
  void reserveDiEdges(int maxEdges) {
    TO.reserve(maxEdges); A.reserve(maxEdges); B.reserve(maxEdges);
  }
  void addDiEdge(int from, int to, T weight) {
    ST[from]++; A.push_back(from); B.push_back(to); C.push_back(weight);
  }
  void addBiEdge(int v, int w, T weight) {
    addDiEdge(v, w, weight); addDiEdge(w, v, weight);
  }
  void build() {
    partial_sum(ST.begin(), ST.end(), ST.begin()); TO = B; WEIGHT = C;
    for (int e = 0; e < int(A.size()); e++) {
      TO[--ST[A[e]]] = B[e]; WEIGHT[ST[A[e]]] = C[e];
    }
  }
  struct Iterator {
    const StaticWeightedGraph &G; int i;
    Iterator(const StaticWeightedGraph &G, int i) : G(G), i(i) {}
    Iterator &operator ++ () { i++; return *this; }
    pair<int, T> operator * () const {
      return make_pair(G.TO[i], G.WEIGHT[i]);
    }
    bool operator != (const Iterator &it) const { return i != it.i; }
  };
  struct Adj {
    const StaticWeightedGraph &G; int v;
    Adj(const StaticWeightedGraph &G, int v) : G(G), v(v) {}
    const Iterator begin() const { return Iterator(G, G.ST[v]); }
    const Iterator end() const { return Iterator(G, G.ST[v + 1]); }
  };
  const Adj operator [] (int v) const { return Adj(*this, v); }
  int size() const { return int(ST.size()) - 1; }
};

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // freopen("err.txt", "w", stderr);
  ios::sync_with_stdio(0); cin.tie(0);
  int N;
  cin >> N;
  StaticWeightedGraph<ll> G(N);
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    G.addBiEdge(--a, --b, c);
  }
  G.build();
  vector<ll> S(N, 0), V(N, 0), ans(N, 0);
  for (int i = 1; i < N; i++) cin >> S[i] >> V[i];
  ConvexHullTrickUndo<i128, greater<i128>> cht;
  cht.reserve(N);
  function<void(int, int, ll)> dfs = [&] (int v, int prev, ll d) {
    if (v > 0) ans[v] = S[v] + d * V[v] + cht.getMax(V[v]);
    cht.addLine(-d, ans[v]);
    for (auto &&[w, weight] : G[v]) if (w != prev) dfs(w, v, d + weight);
    cht.undo();
  };
  dfs(0, -1, 0);
  for (int i = 1; i < N; i++) {
    if (i > 1) cout << sp;
    cout << ans[i];
  }
  cout << nl;
  return 0;
}

• Subtask 1: 100 / 100