Submission #973772

#TimeUsernameProblemLanguageResultExecution timeMemory
973772duckindogHarbingers (CEOI09_harbingers)C++17
50 / 100
1077 ms23496 KiB
#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; vector<pair<int, Line>> save; void add(Line line) { int preTop = top; Line preLine; while (top > 1 && hull[top].x(hull[top - 1]) >= hull[top].x(line)) { preLine = hull[top--]; } save.push_back({preTop, preLine}); 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}); for (const auto& [v, w] : ad[u]) { if (v == p) continue; d[v] = d[u] + w; dfs(v, u); } if (convex.save.size()) { auto[top, line] = convex.save.end()[-1]; convex.hull[convex.top] = line; convex.top = top; convex.save.pop_back(); } } 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]; }

Compilation message (stderr)

harbingers.cpp:13:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   13 |   double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
      |                  ^~~~
harbingers.cpp: In member function 'long long int CHT::query(int)':
harbingers.cpp:36:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |       int mid = l + r >> 1;
      |                 ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...