Submission #718409

#TimeUsernameProblemLanguageResultExecution timeMemory
718409OzyHarbingers (CEOI09_harbingers)C++17
10 / 100
160 ms26428 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define repa(i,a,b) for(int i = (a); i >= (b); i--) #define lli int #define pll pair<lli,lli> #define MAX 100000 // para los hijos #define des first #define w second //para el arreglo de lin #define prep first #define vel second //para el convex hull #define m first #define ord second lli n,a,b,c; vector<pll> hijos[MAX+2]; pll lin[MAX+2],ch[MAX+2]; long double anterior[MAX+2]; lli ancestros[MAX+2][20]; lli dp[MAX+2],prof[MAX+2],rp[MAX+2]; long double cruce(pll a, pll b) { long double u = a.ord - b.ord; long double v = b.m - a.m; u /= v; return u; } void solve(lli pos, lli padre, lli p) { prof[pos] = p; ancestros[pos][0] = padre; rep(i,1,18) { ancestros[pos][i] = ancestros[padre][i-1]; padre = ancestros[pos][i]; } // responde la pregunta para mi posicion /*lli deb = pos; debug(pos); while(deb != 0) { deb = ancestros[deb][0]; debugsl(ch[deb].ord); debugsl(ch[deb].m); debug(anterior[deb]); }*/ lli x = pos; repa(i,18,0) if (anterior[ancestros[x][i]] > (long double)lin[pos].vel) x = ancestros[x][i]; x = ancestros[x][0]; dp[pos] = lin[pos].prep + prof[pos]*lin[pos].vel + dp[x] - prof[x]*lin[pos].vel; //hago mi propia línea ch[pos].ord = dp[pos]; ch[pos].m = -prof[pos]; //debugsl(ch[pos].m); //debug(ch[pos].ord); lli dir; //caso donde seguro no entro en ninguna parte del convex hull if (ch[ancestros[pos][0]].m <= ch[pos].m) dir = padre; else { dir = pos; //proceso contra el convex hull trick x = pos; repa(i,18,0) if (cruce(ch[x], ch[ancestros[x][i]]) <= anterior[ancestros[x][i]]) x = ancestros[x][i]; ancestros[pos][0] = ancestros[x][0]; anterior[pos] = cruce(ch[pos],ch[ancestros[pos][0]]); x = ancestros[x][0]; rep(i,1,18) { ancestros[pos][i] = ancestros[x][i-1]; x = ancestros[pos][i]; } } for(auto h : hijos[pos]) { if (h.des == rp[pos]) continue; rp[h.des] = pos; solve(h.des,dir,p+h.w); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; rep(i,2,n) { cin >> a >> b >> c; hijos[a].push_back({b,c}); hijos[b].push_back({a,c}); } rep(i,2,n) cin >> lin[i].prep >> lin[i].vel; for (auto h : hijos[1]) { rp[h.des] = 1; solve(h.des,0,h.w); } rep(i,2,n) cout << dp[i] << ' '; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...