Submission #1278692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278692		gr17	Harbingers (CEOI09_harbingers)	C++20	100 / 100	93 ms	22064 KiB

harbingers

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef MY_DEBUG
#include "debug.h"
#endif
#ifdef MY_DEBUG
#define debug(...)                \
  std::cerr << __LINE__ << ": [", \
      __DEBUG_UTIL__::printer(#__VA_ARGS__, __VA_ARGS__)
#define debugArr(...)             \
  std::cerr << __LINE__ << ": [", \
      __DEBUG_UTIL__::printerArr(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#define debugArr(...)
#endif
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define T0(x) get<0>(x)
#define T1(x) get<1>(x)
#define T2(x) get<2>(x)
#define T3(x) get<3>(x)
#define T4(x) get<4>(x)
#define T5(x) get<5>(x)
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> t3;
#define FR(i, n) for (ll i = 0, __nend__##i = ll(n); i < __nend__##i; ++i)
#define FOR(i, a, b) \
  for (ll i = (a), __nend__##i = ll(b); i <= __nend__##i; ++i)
#define FORD(i, a, b) \
  for (ll i = (a), __nend__##i = ll(b); i >= __nend__##i; --i)
#define v1ll vector<ll>
#define v2ll vector<v1ll>
#define v3ll vector<v2ll>
#define v4ll vector<v3ll>
#define mk_v1ll(n, x) vector<ll>(n, x)
#define mk_v2ll(n, m, x) vector<v1ll>(n, mk_v1ll(m, x))
#define mk_v3ll(n, m, l, x) vector<v2ll>(n, mk_v2ll(m, l, x))
#define mk_v4ll(n, m, l, k, x) vector<v3ll>(n, mk_v3ll(m, l, k, x))
template <typename T>
auto mk_v1(ll n, const T& x) {
  return vector<T>(n, x);
}
template <typename T>
auto mk_v2(ll n, ll m, const T& x) {
  return vector<vector<T>>(n, mk_v1(m, x));
}
template <typename T>
auto mk_v3(ll n, ll m, ll l, const T& x) {
  return vector<vector<vector<T>>>(n, mk_v2(m, l, x));
}
template <typename T>
auto mk_v4(ll n, ll m, ll l, ll k, const T& x) {
  return vector<vector<vector<vector<T>>>>(n, mk_v3(m, l, k, x));
}
#define getBit(n, i) (((n) >> (i)) & 1ll)
#define setBit(n, i) ((n) | (1ll << (i)))
#define clearBit(n, i) ((n) & ~(1ll << (i)))
#define flipBit(n, i) ((n) ^ (1ll << (i)))
std::mt19937_64 Rng{static_cast<unsigned long long>(
    std::chrono::steady_clock::now().time_since_epoch().count())};
constexpr ll MyP = 1000000021ll;
constexpr ll MyPrime = 1000000033ll;
constexpr ll MyPrime2 = 1000000087ll;
const ld PI = acos(ld(-1));
#define UNUSED(x) (void)x
#define endl '\n'
#ifdef LOCAL
#define cin fin
#endif

template <class T, class T2>
struct PairHash {
  std::size_t operator()(const std::pair<T, T2>& p) const {
    auto hash1 = std::hash<T>{}(p.first);
    auto hash2 = std::hash<T2>{}(p.second);
    return hash1 ^ (hash2 + 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2));
  }
};

template <class F>
struct __FixPoint : private F {
  constexpr __FixPoint(F&& f) : F(std::forward<F>(f)) {}
  template <class... T>
  constexpr auto operator()(T&&... x) const {
    return F::operator()(*this, std::forward<T>(x)...);
  }
};

struct __MakeFixPoint {
  template <class F>
  constexpr auto operator|(F&& f) const {
    return __FixPoint<F>(std::forward<F>(f));
  }
};

#define __MFP __MakeFixPoint() |

#ifdef __GNUC__
#define __GPOP _Pragma("GCC diagnostic pop") _Pragma("GCC diagnostic pop")
#else
#define __GPOP
#endif

#ifdef __GNUC__
#define def(name, ...)                                                        \
  _Pragma("GCC diagnostic push") _Pragma(                                     \
      "GCC diagnostic ignored \"-Wshadow\"") _Pragma("GCC diagnostic push")   \
      _Pragma(                                                                \
          "GCC diagnostic ignored \"-Wunused-but-set-variable\"") auto name = \
          __MFP[&](auto&& name, __VA_ARGS__)
#else
#define def(name, ...) auto name = __MFP[&](auto&& name, __VA_ARGS__)
#endif

#ifdef _MSC_VER
#pragma warning(disable : 4996)
#endif

#define REOPEN(input, output) \
  freopen(input, "r", stdin); \
  freopen(output, "w", stdout);
#define _All(x) (x).begin(), (x).end()

template <class T1, class T2>
bool umin(T1& t1, T2&& t2) {
  if (t1 > t2) {
    t1 = std::forward<T2>(t2);
    return true;
  }
  return false;
}

template <class T1, class T2>
bool umax(T1& t1, T2&& t2) {
  if (t1 < t2) {
    t1 = std::forward<T2>(t2);
    return true;
  }
  return false;
}

#define REOPEN(input, output) \
  freopen(input, "r", stdin); \
  freopen(output, "w", stdout);
#define _All(x) (x).begin(), (x).end()
template <class T>
T f(T x, const v1ll& h, const v1ll& c) {
  T ss = 0;
  FR(i, h.size()) ss += abs(h[i] - x) * c[i];
  return -ss;
};

#include <iostream>
#include <vector>
using namespace std;

namespace line_container_undo {
typedef long long ll;

typedef pair<ll, ll> Line;

const int N = 1e5 + 9;
const ll INF = (ll)1e18;

struct operation {
  int pos, top;
  Line overwrite;
  operation(int _p, int _t, Line _o) {
    pos = _p;
    top = _t;
    overwrite = _o;
  }
};
vector<operation> undoLst;
Line lines[N];
int top = 0;

ll eval(Line line, ll x) { return line.first * x + line.second; }
bool bad(Line a, Line b, Line c) {
  return (double)(b.second - a.second) / (a.first - b.first) >=
         (double)(c.second - a.second) / (a.first - c.first);
}

ll getMin(ll coord) {
  int l = 0, r = top - 1;
  ll ans = eval(lines[l], coord);
  while (l < r) {
    int mid = (l + r) >> 1;
    ll x = eval(lines[mid], coord);
    ll y = eval(lines[mid + 1], coord);
    if (x > y)
      l = mid + 1;
    else
      r = mid;
    ans = min(ans, min(x, y));
  }
  return ans;
}

bool insertLine(Line newLine) {
  int l = 1, r = top - 1, k = top;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (bad(lines[mid - 1], lines[mid], newLine)) {
      k = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  undoLst.push_back(operation(k, top, lines[k]));
  top = k + 1;
  lines[k] = newLine;
  return true;
}

void undo() {
  operation ope = undoLst.back();
  undoLst.pop_back();
  top = ope.top;
  lines[ope.pos] = ope.overwrite;
}

}  // namespace line_container_undo

int main() {
  UNUSED(MyPrime);
  UNUSED(MyPrime2);
  UNUSED(MyP);
#ifndef LOCAL
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
#else
  auto startTime = chrono::steady_clock::now();
  ifstream fin("_i.txt");
#endif
  ll n;
  cin >> n;

  vector<vector<pll>> g(n);
  FR(i, n - 1) {
    ll u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  v1ll s(n), v(n);
  FOR(i, 1, n - 1) cin >> s[i] >> v[i];

  v1ll depth(n);
  v1ll ans(n);

  def(dfs, ll u, ll pa, ll dep)->void {
    depth[u] = dep;
    if (u != 0) {
      ans[u] = depth[u] * v[u] + s[u] + line_container_undo::getMin(v[u]);

      line_container_undo::insertLine({-depth[u], ans[u]});
    } else
      line_container_undo::insertLine({0, 0});
    for (auto [v, w] : g[u])
      if (v != pa) {
        dfs(v, u, dep + w);
      }

    line_container_undo::undo();
  };

  dfs(0, -1, 0);

  FOR(i, 1, n - 1) cout << ans[i] << " ";

#ifdef LOCAL
  fin.close();
  auto endTime = chrono::steady_clock::now();
  auto diff = endTime - startTime;
  cerr << endl;
  cerr << "Time :" << chrono::duration<double, milli>(diff).count() << " ms"
       << endl;
#endif
  return 0;
}

• Subtask 1: 100 / 100