Submission #1105316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105316		zNatsumi	Harbingers (CEOI09_harbingers)	C++17	100 / 100	85 ms	30024 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ii pair<int, int>
#define fi first
#define se second

const int N = 1e5 + 5,
          INF = 1e18;

int n, S[N], V[N], dep[N], dp[N];
vector<ii> ad[N];

void cal_depth(int u, int p){
  for(auto [v, w] : ad[u]) if(v != p){
    dep[v] = dep[u] + w;
    cal_depth(v, u);
  }
}

bool ok = false;

struct Line{
  int a, b; // y = a*x + b;
  Line(){}
  Line(int a, int b): a(a), b(b) {}
  double x(Line rhs){ return 1.0*(b - rhs.b)/(rhs.a - a); }
  int valy(int x){ return a * x + b; }

  friend ostream& operator << (ostream& os, Line &rhs){
    return os << "(" << rhs.a << ", " << rhs.b << ")";
  }
};

struct CHT{
  Line convex[N];
  pair<Line*, Line> rl[N];
  pair<int*, int> rp[N];
  int bot = 1, top = 0, it = 0;

  int add(Line line){
    rp[it] = {&top, top};

    int l = bot, r = top, k = top + 1;
    while(l <= r){
      int mid = l + r >> 1;
      if(convex[mid - 1].x(convex[mid]) > convex[mid - 1].x(line)) r = (k = mid) - 1;
      else l = mid + 1;
    }
    top = k;
    rl[it] = {convex + top, convex[top]};
    convex[top] = line;
    it++;

    return it - 1;
  }
  void rollback(int t){
    for(; it > t;){
      --it;
      *rl[it].first = rl[it].second;
      *rp[it].first = rp[it].second;
    }
  }
  int query(int x){
    int l = bot, r = top, res = convex[l].valy(x);

    while(l <= r){
      int mid = l + r >> 1;

      int y1 = convex[mid].valy(x),
          y2 = convex[mid + 1].valy(x);
      if(y1 > y2) l = mid + 1;
      else r = mid - 1;
      res = min({res, y1, y2});
    }
    return res;
  }
} cht;

void dfs(int u, int p){
  int it = cht.add(Line(-dep[u], dp[u]));

  for(auto [v, w] : ad[u]) if(v != p){
    dp[v] = cht.query(V[v]) + dep[v] * V[v] + S[v];
    dfs(v, u);
  }
  cht.rollback(it);
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n;
  for(int i = 2; i <= n; i++){
    int u, v, w; cin >> u >> v >> w;
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
  }
  for(int i = 2; i <= n; i++) cin >> S[i] >> V[i];
  cal_depth(1, -1);
  dfs(1, -1);
  for(int i = 2; i <= n; i++) cout << dp[i] << " ";

  return 0;
}

Compilation message (stderr)

harbingers.cpp: In member function 'long long int CHT::add(Line)':
harbingers.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |       int mid = l + r >> 1;
      |                 ~~^~~
harbingers.cpp: In member function 'long long int CHT::query(long long int)':
harbingers.cpp:69:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |       int mid = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 100 / 100