Submission #813715

#	Time	Username	Problem	Language	Result	Execution time	Memory
813715		jun6873	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1090 ms	26840 KiB

harbingers

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

using lint = long long;
using pint = pair<lint, lint>;
#define x first
#define y second

struct cht {
  lint a[100004], b[100004];
  int cnt = 0;

  struct record {
    int cnt, i;
    lint a, b;
  };
  vector<record> rec;

  void update(lint a0, lint b0) {
    record r;
    r.cnt = cnt;

    while (cnt >= 2 and (b[cnt] - b[cnt - 1]) * (__int128)(a0 - a[cnt]) <=
                            (b0 - b[cnt]) * (__int128)(a[cnt] - a[cnt - 1]))
      cnt--;
    cnt++;

    r.i = cnt;
    r.a = a[cnt];
    r.b = b[cnt];

    a[cnt] = a0;
    b[cnt] = b0;

    rec.push_back(r);
  }

  void undo() {
    record r = rec.back();
    rec.pop_back();

    cnt = r.cnt;
    a[r.i] = r.a;
    b[r.i] = r.b;
  }

  lint f(int i, lint x) { return a[i] * x + b[i]; }
  lint query(lint x) {
    if (cnt == 0) return 0;
    int l = 0, r = cnt;
    while (l + 1 < r) {
      int m = (l + r) / 2;
      if ((b[m + 1] - b[m]) < -x * (__int128)(a[m + 1] - a[m]))
        l = m;
      else
        r = m;
    }
    return a[r] * x + b[r];
  }
} t;

int N;
lint dep[100004], s[100004], v[100004], dp[100004];

vector<pint> g[100004];

void dfs0(int x, int p) {
  for (auto [y, w] : g[x])
    if (y != p) {
      dep[y] = dep[x] + w;
      dfs0(y, x);
    }
}

void dfs(int x, int p) {
  dp[x] = t.query(v[x]) + s[x] + dep[x] * v[x];

  t.update(-dep[x], dp[x]);

  for (auto [y, w] : g[x])
    if (y != p) {
      dfs(y, x);
    }

  t.undo();
}

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

  cin >> N;
  for (int i = 1; i < N; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }

  for (int i = 2; i <= N; i++) cin >> s[i] >> v[i];

  dfs0(1, 1);
  dfs(1, 1);

  for (int i = 2; i <= N; i++) cout << dp[i] << ' ';
  cout << '\n';
}

• Subtask 1: 70 / 100