Submission #973827

#	Time	Username	Problem	Language	Result	Execution time	Memory
973827		duckindog	Harbingers (CEOI09_harbingers)	C++17	100 / 100	75 ms	24912 KiB

harbingers

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100'000 + 1;
int n;
vector<pair<int, int>> ad[N];
int s[N], velocity[N];
int d[N];
 
struct Line { 
  long long a, b;
  double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
};
struct CHT { 
  int top;
  array<Line, N> hull;
  array<pair<int, Line>, N> save;

  void add(Line line, int u) { 
    int preTop = top;
    int l = 2, r = top; top += 1;
    while (l <= r) { 
      int mid = l + r >> 1;
      if (hull[mid].x(hull[mid - 1]) >= hull[mid].x(line)) r = (top = mid) - 1;
      else l = mid + 1;
    }
    save[u] = {preTop, hull[top]};
    hull[top] = line;
  }

  long long query(int u) { 
    auto cal = [&](int it) { 
      return hull[it].a * velocity[u] + hull[it].b + 1ll * d[u] * velocity[u] + s[u];
    };
     
    int l = 1, r = top - 1, it = 1;
    while (l <= r) { 
      int mid = l + r >> 1;
      if (cal(mid) >= cal(mid + 1)) l = it = mid + 1;
      else r = mid - 1;
    }
    return cal(it);
  }
} convex;
 
long long dp[N];
void dfs(int u, int p = 0) {  
  auto& ret = dp[u];
  ret = min(ret, convex.query(u));
  convex.add({-d[u], ret}, u);

  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    d[v] = d[u] + w;
    dfs(v, u);
  }
  
  auto[top, line] = convex.save[u];
  convex.hull[convex.top] = line;
  convex.top = top;
}
 
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] >> velocity[i];
 
  memset(dp, 40, sizeof dp);
  dfs(1);
  
  for (int i = 2; i <= n; ++i) cout << dp[i] << " \n"[i == n];
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
}

Compilation message (stderr)

harbingers.cpp:15:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 |   double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
      |                  ^~~~
harbingers.cpp: In member function 'void CHT::add(Line, int)':
harbingers.cpp:26:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |       int mid = l + r >> 1;
      |                 ~~^~~
harbingers.cpp: In member function 'long long int CHT::query(int)':
harbingers.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |       int mid = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 100 / 100