제출 #1283887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283887		bahy	Harbingers (CEOI09_harbingers)	C++20	0 / 100	202 ms	131072 KiB

harbingers

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

const int N = 1e5 + 10;
const int inf = 1e9 + 10;

struct Line {
  ll k, d;
  ll eval(ll x) {
    return k * x + d;
  }
};

struct LiChaoNode {
  Line line;
  int l, r;
  LiChaoNode() {
    line = Line({0, numeric_limits<long long>::max() / 2});
    l = 0, r = 0;
  }
  LiChaoNode(Line line) : line(line), l(0), r(0) {}
} t[50 * N];

int T;
int upd(int pre, Line nw, int l, int r) {
  int m = (l + r) / 2;
  int id = ++T;
  t[id].line = t[pre].line;
  bool lef = nw.eval(l) < t[id].line.eval(l);
  bool mid = nw.eval(m) < t[id].line.eval(m);
  if(mid) swap(t[id].line, nw);
  if(l == r) return id;
  if(lef != mid) {
    if(!t[pre].l) t[id].l = ++T, t[T] = LiChaoNode(nw);
    else t[id].l = upd(t[pre].l, nw, l, m);
    t[id].r = t[pre].r;
  } else {
    if(!t[pre].r) t[id].r = ++T, t[T] = LiChaoNode(nw);
    else t[id].r = upd(t[pre].r, nw, m + 1, r);
    t[id].l = t[pre].l;
  }
  return id;
}

ll Query(int cur, int x, int l, int r) {
  ll val = t[cur].line.eval(x);
  int m = (l + r) / 2;
  if(l < r) {
    if(x <= m && t[cur].l) val = min(val, Query(t[cur].l, x, l, m));
    if(x > m && t[cur].r) val = min(val, Query(t[cur].r, x, m + 1, r));
  }
  return val;
}

struct PersistentLiChaoTree {
  int L, R;
  vector<int> roots;
  PersistentLiChaoTree() {
    roots = {1};
    T = 1;
    L = -1e9;
    R = 1e9;
  }
  PersistentLiChaoTree(int L, int R) : L(L), R(R) {
    T = 1;
    roots.push_back(1);
  }
  void add_line(Line line) {
    int root = upd(roots.back(), line, L, R);
    roots.push_back(root);
  }
  ll query(int i, int x) {
    return Query(roots[i], x, L, R);
  }
} lt;

int n;
vector<vector<array<int, 2>>> adj;
ll s[N], v[N], sum[N], dp[N];

void dfs(int cur, int par){
    for(auto [i, d]: adj[cur]){
        if(i == par)continue;
        sum[i] = sum[cur] + d;
        dfs(i, cur);
    }
}

void calc(int cur, int par){
    for(auto [i, d]: adj[cur]){
        if(i == par)continue;
        dp[i] = sum[i] * v[i] + s[i] + lt.query(lt.roots.size() - 1, v[i]);
        lt.add_line({-sum[i], dp[i]});
        calc(i, cur);
        lt.roots.pop_back();
    }
}

void solve() {
    cin >> n;
    adj.assign(n + 1, vector<array<int, 2>>());

    for(int i = 0; i < n - 1; i++){
        int u, v, d; cin >> u >> v >> d;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }

    dfs(1, 0);

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

    lt.add_line({0, 0});
    
    calc(1, 0);

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

int main(){
    ios_base::sync_with_stdio(0);
    // freopen("harbingers.in", "r", stdin);
    // freopen("harbingers.out", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

• Subtask 1: 0 / 100