제출 #641506

#제출 시각아이디문제언어결과실행 시간메모리
641506sumit_kk10Harbingers (CEOI09_harbingers)C++17
90 / 100
125 ms21964 KiB
#include<bits/stdc++.h> #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) #define pb push_back #define F first #define S second #define int long long using namespace std; const int N = 1e5 + 5, MOD = 1e9 + 7; vector<pair<int, int> > g[N]; int n, par[N], dis[N], dp[N], s[N], d[N]; struct Line{ int m, c; int val(int x){ return m*x + c; } }; vector<Line> hulls(N); int cur_hullsize = 1; long double intersect(Line l1, Line l2){ return (long double)(l2.c - l1.c) / (long double)(l1.m - l2.m); } int pos(int mm, int cc){ Line cur; cur.m = mm; cur.c = cc; if(cur_hullsize < 2 or (intersect(cur, hulls[cur_hullsize - 1]) > intersect(hulls[cur_hullsize - 1], hulls[cur_hullsize - 2]))) return cur_hullsize; int low = 1, high = cur_hullsize - 1, ans = 0; while(low <= high){ int mid = (low + high) / 2; if(intersect(cur, hulls[mid]) < intersect(hulls[mid], hulls[mid - 1])){ ans = mid; high = mid - 1; } else low = mid + 1; } return ans; } int get(int x){ int low = 0, high = cur_hullsize - 1; while(low < high){ int mid = (low + high) / 2; if(hulls[mid].val(x) < hulls[mid + 1].val(x)) high = mid; else low = mid + 1; } return hulls[high].val(x); } void dfs(int node, int p, int sum){ dis[node] = sum; par[node] = p; for(auto k : g[node]){ if(k.F == p) continue; dfs(k.F, node, sum + k.S); } } /* we want to find the position in the convex hull where the current line will go we will replace that position with the current line we will change it back once I go up from that node */ void dfs1(int node){ dp[node] = get(d[node]) + s[node] + dis[node] * d[node]; int cur, here = cur_hullsize; Line pre; if(node != 1){ cur = cur_hullsize = pos(-dis[node], dp[node]); Line neww; neww.m = -dis[node]; neww.c = dp[node]; pre = hulls[cur]; hulls[cur] = neww; cur_hullsize++; } for(auto k : g[node]){ if(k.F == par[node]) continue; dfs1(k.F); } if(node != 1){ cur_hullsize = here; hulls[cur] = pre; } } void solve(){ cin >> n; for(int i = 1; i < n; ++i){ int u, v, c; cin >> u >> v >> c; g[u].pb({v, c}); g[v].pb({u, c}); } for(int i = 1; i < n; ++i) cin >> s[i + 1] >> d[i + 1]; dfs(1, 0, 0); Line wut; wut.m = 0, wut.c = 0; hulls[0] = wut; dfs1(1); for(int i = 2; i <= n; ++i) cout << dp[i] << " "; } int32_t main(){ fast; int t = 1; // cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...