Submission #641333

#TimeUsernameProblemLanguageResultExecution timeMemory
641333sumit_kk10Harbingers (CEOI09_harbingers)C++17
50 / 100
149 ms65536 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]; bool vis[N]; struct Line{ int m, c; int val(int x){ return m*x + c; } }; vector<pair<Line, int> > hulls; vector<pair<Line, int> > removed[N]; bool check(Line a, Line b, Line cc){ int x = (b.c - a.c); x = x * (a.m - cc.m); int y = (cc.c - a.c); y = y * (a.m - b.m); if(x > y) return true; return false; } void insert(int mm, int cc, int node){ Line cur; cur.m = mm; cur.c = cc; if(!hulls.empty() and hulls.back().F.m == mm){ if(hulls.back().F.c > cc){ vis[hulls.back().S] = false; removed[node].pb(hulls.back()); hulls.pop_back(); } else{ vis[node] = false; return; } } while(hulls.size() > 1){ if(check(hulls[hulls.size() - 2].F, hulls.back().F, cur)){ vis[hulls.back().S] = false; removed[node].pb(hulls.back()); hulls.pop_back(); } else break; } reverse(removed[node].begin(), removed[node].end()); hulls.pb({cur, node}); } int get(int x){ if(hulls.empty()) return 1e15; int low = 0, high = (int) hulls.size() - 2, ans = (int) hulls.size() - 1; while(low <= high){ int mid = (low + high) / 2; if(hulls[mid].F.val(x) <= hulls[mid + 1].F.val(x)){ ans = mid; high = mid - 1; } else low = mid + 1; } return hulls[ans].F.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); } } void dfs1(int node){ int mn = s[node] + dis[node] * d[node]; mn = min(mn, get(d[node]) + s[node] + dis[node] * d[node]); dp[node] = mn; if(node != 1){ vis[node] = true; insert(-dis[node], dp[node], node); } for(auto k : g[node]){ if(k.F == par[node]) continue; dfs1(k.F); } if(vis[node]) hulls.pop_back(); for(auto k : removed[node]){ vis[k.S] = true; insert(k.F.m, k.F.c, k.S); } } 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); 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...