Submission #1210418

#TimeUsernameProblemLanguageResultExecution timeMemory
1210418dostsHarbingers (CEOI09_harbingers)C++20
10 / 100
3 ms2884 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9; const int N = 2500+1; vi s(N),v(N),d(N),dp(N); vector<pii> edges[N]; struct Line { int m,b; int eval(int x) { return m*x+b; } }; vector<Line> lines; stack<pair<Line&,Line>> upds; vi lft,rgt; int ids = 0; struct LiChao { int crenode() { lines.push_back({inf,inf}); lft.push_back(-1); rgt.push_back(-1); ids++; return ids-1; } int leftchild(int node) { if (lft[node] == -1) lft[node] = crenode(); return lft[node]; } int rightchild(int node) { if (rgt[node] == -1) rgt[node] = crenode(); return rgt[node]; } void update(int node, int l,int r,Line line) { if (line.m == inf && line.b == inf) return; int m = (l+r) >> 1; bool good = lines[node].eval(l) > line.eval(l); bool goodmid = lines[node].eval(m) > line.eval(m); if (goodmid) { upds.push({lines[node],lines[node]}); swap(lines[node],line); } if (l == r) return; if (goodmid != good) update(leftchild(node),l,m,line); else update(rightchild(node),m+1,r,line); }; int query(int node,int l,int r,int x) { if (l == r) return lines[node].eval(x); int m = (l+r) >> 1; if (x <= m) return min(lines[node].eval(x),query(leftchild(node),l,m,x)); return min(lines[node].eval(x),query(rightchild(node),m+1,r,x)); } void rollback(int k) { while (k--) { pair<Line&,Line> p = upds.top(); upds.pop(); p.ff = p.ss; } } }LC; void dfs(int node,int p,int der = 0) { d[node] = der; if (node > 1) { dp[node] = s[node]+v[node]*d[node]+LC.query(0,0,1000000000,v[node]); } else dp[node] = 0; int crea = upds.size(); LC.update(0,0,1000000000,{-d[node],dp[node]}); int crea2 = upds.size(); for (auto it : edges[node]) { if (it.ff == p) continue; dfs(it.ff,node,der+it.ss); } //LC.rollback(crea2-crea); } void solve() { int n; cin >> n; for (int i=1;i<n;i++) { int a,b,c; cin >> a >> b >> c; edges[a].push_back({b,c}); edges[b].push_back({a,c}); } for (int i=2;i<=n;i++) cin >> s[i] >> v[i]; int root = LC.crenode(); dfs(1,1); for (int i=2;i<=n;i++) cout << dp[i] << ' '; cout << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef Dodi freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...