Submission #885764

#TimeUsernameProblemLanguageResultExecution timeMemory
885764peterandvoiHarbingers (CEOI09_harbingers)C++17
20 / 100
72 ms41152 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define db(...) " [" << #__VA_ARGS__ << " : " << (__VA_ARGS__) << "] " const int N = 100005; int n; int s[N], c[N]; long long dp[N], d[N]; vector<pair<int, int>> g[N]; long long Div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); } struct Line { long long k, m; Line() {}; Line(long long k, long long m): k(k), m(m) {}; long long eval(long long x) const { return k * x + m; } friend bool bad(const Line &a, const Line &b, const Line &c) { return Div(b.m - a.m, a.k - b.k) >= Div(c.m - a.m, a.k - c.k); } }; struct convex_hull_rollback { int n = 0; Line a[N]; stack<tuple<int, Line>> st; void add(long long k, long long m) { Line x = {k, m}; int l = 2, r = n, pos = n + 1; while (l <= r) { int mid = l + r >> 1; if (bad(a[mid - 1], a[mid], x)) { r = mid - 1; pos = mid; } else { l = mid + 1; } } st.emplace(n, a[n]); n = pos; a[n] = x; } long long query(long long x) { int l = 2, r = n, pos = 1; while (l <= r) { int mid = l + r >> 1; if (a[mid - 1].eval(x) > a[mid].eval(x)) { pos = mid; l = mid + 1; } else { r = mid - 1; } } return a[pos].eval(x); } void rollback() { auto [prv, l] = st.top(); st.pop(); a[n] = l; n = prv; } }; convex_hull_rollback cht; void dfs(int u = 1, int par = 1) { if (u != 1) { dp[u] = cht.query(c[u]) + 1LL * d[u] * c[u] + s[u]; } cht.add(-d[u], dp[u]); for (auto [v, w] : g[u]) { if (v != par) { d[v] = d[u] + w; dfs(v, u); } } cht.rollback(); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1, u, v, w; i < n; ++i) { cin >> u >> v >> w; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } for (int i = 2; i <= n; ++i) { cin >> s[i] >> c[i]; } dfs(); for (int i = 2; i <= n; ++i) { cout << dp[i] << " "; } }

Compilation message (stderr)

harbingers.cpp: In member function 'void convex_hull_rollback::add(long long int, long long int)':
harbingers.cpp:45:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |       int mid = l + r >> 1;
      |                 ~~^~~
harbingers.cpp: In member function 'long long int convex_hull_rollback::query(long long int)':
harbingers.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |       int mid = l + r >> 1;
      |                 ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...