제출 #579921

#제출 시각아이디문제언어결과실행 시간메모리
579921leeh18Harbingers (CEOI09_harbingers)C++17
100 / 100
128 ms25128 KiB
#include <bits/stdc++.h> template<class Fun> class y_combinator_result { Fun fun_; public: template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } using namespace std; using ll = long long; struct line { ll a, b; line(ll a_, ll b_) : a(a_), b(b_) {} line() : a(0LL), b(0LL) {} ll operator()(ll x) const { return a * x + b; } }; ll floor_div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } ll intersect(const line& l1, const line& l2) { return floor_div(l2.b - l1.b, l1.a - l2.a); } signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int N; cin >> N; vector<vector<pair<int, ll>>> adj(N+1); for (int i = 0; i < N-1; i++) { int U, V, D; cin >> U >> V >> D; assert(D > 0); adj[U].emplace_back(V, (ll)D); adj[V].emplace_back(U, (ll)D); } vector<ll> S(N+1), V(N+1); for (int i = 2; i <= N; i++) { cin >> S[i] >> V[i]; } vector<ll> dp(N+1); vector<line> st(N+2); int p = 1; auto dfs = y_combinator([&](auto self, int u, int parent, ll dist) -> void { if (u == 1) { for (auto [v, w] : adj[u]) { if (v != parent) { self(v, u, dist+w); } } return; } int lo = 0, hi = p - 1; ll x = V[u]; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (intersect(st[mid-1], st[mid]) < x) lo = mid; else hi = mid - 1; } dp[u] = S[u] + V[u] * dist - st[lo](x); line cur(dist, -dp[u]); lo = 1, hi = p; while (lo < hi) { int mid = (lo + hi) / 2; if (intersect(cur, st[mid]) <= intersect(st[mid], st[mid-1])) { hi = mid; } else { lo = mid + 1; } } auto prev_line = st[lo]; int prev_p = p; st[lo] = cur; p = lo + 1; for (auto [v, w] : adj[u]) { if (v != parent) { self(v, u, dist+w); } } st[lo] = prev_line; p = prev_p; }); dfs(1, 1, 0); for (int i = 2; i <= N; i++) { cout << dp[i] << " \n"[i == N]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...