Submission #660311

#TimeUsernameProblemLanguageResultExecution timeMemory
660311leroycutHarbingers (CEOI09_harbingers)C++17
100 / 100
147 ms23488 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 1e5 + 3; const ll INF = 2e12 + 3; struct LINE{ ll k = 0, b = 0; LINE(ll _k = 0, ll _b = 0) : k(_k), b(_b) {} }; ld cross(LINE a, LINE b){ return (ld)(b.b - a.b) / (ld)(a.k - b.k); } ll f(LINE a, ll x){ return a.k * x + a.b; } int n, st_end = 0; ll V[N], S[N], dp[N]; vector<pair<int, ll>> g[N]; LINE st[N]; ll min_val(ll x){ int l = -1, r = st_end - 1; while(r - l > 1){ int m = (l + r) / 2; if(cross(st[m], st[m + 1]) <= x){ l = m; }else{ r = m; } } return f(st[l + 1], x); } int remove_el(LINE cur){ if(st_end < 2 || cross(st[st_end - 1], cur) >= cross(st[st_end - 1], st[st_end - 2])){ return st_end; } int l = 1, r = st_end - 1; while(r - l > 0){ int m = (l + r) / 2; if(cross(st[m], cur) < cross(st[m], st[m - 1])){ r = m; }else{ l = m + 1; } } return l; } void dfs(int v, int p, ll d){ int prev_pos, prev_st_end; LINE prev_line; if(p == 0){ dp[v] = 0; st[st_end++] = {0, 0}; }else{ dp[v] = S[v] + d * V[v] + min_val(V[v]); LINE cur(-d, dp[v]); prev_st_end = st_end; prev_pos = st_end = remove_el(cur); prev_line = st[st_end]; st[st_end++] = cur; } for(auto i : g[v]){ if(i.first == p) continue; dfs(i.first, v, d + i.second); } if(p != 0){ st[prev_pos] = prev_line; st_end = prev_st_end; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n - 1; ++i){ int a, b, c; cin >> a >> b >> c; g[a].push_back({b, c}); g[b].push_back({a, c}); } for(int i = 2; i <= n; ++i){ cin >> S[i] >> V[i]; } dfs(1, 0, 0); for(int i = 2; i <= n; ++i){ cout << dp[i] << " "; } cout << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...