Submission #1087802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087802		juicy	Harbingers (CEOI09_harbingers)	C++17	100 / 100	67 ms	19908 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

struct line {
  long long a, b;

  long long div(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b);
  }

  long long slope(const line &o) {
    return div(o.b - b, a - o.a);
  }

  long long eval(long long x) {
    return a * x + b;
  }
};

const int N = 1e5 + 5;

int n, top;
int S[N], V[N];
long long dp[N];
line st[N];
vector<pair<int, line>> his;
vector<array<int, 2>> g[N];

void add(line x) {
  int l = 2, r = top, res = top + 1;
  while (l <= r) {
    int m = (l + r) / 2;
    if (st[m - 1].slope(st[m]) >= st[m].slope(x)) {
      res = m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  his.push_back({top, st[res]});
  st[top = res] = x;
}

long long qry(long long x) {
  int l = 2, r = top, p = 1;
  while (l <= r) {
    int m = (l + r) / 2;
    if (st[m - 1].slope(st[m]) < x) {
      p = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return st[p].eval(x);
}

void dfs(int u, int p = 0, long long dep = 0) {
  if (u ^ 1) {
    dp[u] = qry(V[u]) + dep * V[u] + S[u];
  }
  add({-dep, dp[u]});
  for (auto [v, w] : g[u]) {
    if (v ^ p) {
      dfs(v, u, dep + w);
    }
  }
  auto [x, l] = his.back(); his.pop_back();
  st[top] = l;
  top = x;
}

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

  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v, d; cin >> u >> v >> d;
    g[u].push_back({v, d});
    g[v].push_back({u, d});
  }
  for (int i = 2; i <= n; ++i) {
    cin >> S[i] >> V[i];
  }
  dfs(1);
  for (int i = 2; i <= n; ++i) {
    cout << dp[i] << " ";
  }
  return 0;
}

• Subtask 1: 100 / 100