Submission #813689

#	Time	Username	Problem	Language	Result	Execution time	Memory
813689		jun6873	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1078 ms	26100 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;
  };
  record r[100004];
  int rcnt = 0;

  void update(lint a0, lint b0) {
    rcnt++;
    r[rcnt].cnt = cnt;

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

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

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

  void undo() {
    cnt = r[rcnt].cnt;
    a[r[rcnt].i] = r[rcnt].a;
    b[r[rcnt].i] = r[rcnt].b;
    rcnt--;
  }

  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 (f(m, x) > f(m + 1, x))
        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