제출 #718727

#제출 시각아이디문제언어결과실행 시간메모리
718727OzyHarbingers (CEOI09_harbingers)C++17
0 / 100
132 ms22864 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 long long int #define pll pair<lli,lli> #define MAX 100000 #define MAXL 16 // 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<pair<int, int> > hijos[MAX+2]; pair<int, int> lin[MAX+2]; pll ch[MAX+2]; lli anterior[MAX+2]; int ancestros[MAXL+1][MAX+2]; lli dp[MAX+2],prof[MAX+2]; int largo[MAX+2],lg[MAX+2]; lli cruce(pll a, pll b) { lli u = a.ord - b.ord; lli v = b.m - a.m; u /= v; return u; } void solve(int pos, int padre, lli p) { prof[pos] = p; // responde la pregunta para mi posicion lli x = padre; repa(i,lg[largo[padre]],0) if (anterior[ancestros[i][x]] >= lin[pos].vel) x = ancestros[i][x]; if (anterior[x] >= lin[pos].vel) x = ancestros[0][x]; 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]; //me integro en el convex hull trick con binaria x = padre; //CAMBIE while (x) //CAMBIE if (cruce(ch[pos], ch[x]) <= anterior[x]) x = ancestros[0][x]; //CAMBIE else break; repa(i,lg[largo[padre]],0) if (cruce(ch[pos], ch[ancestros[i][x]]) <= anterior[ancestros[i][x]]) x = ancestros[0][ancestros[i][x]]; if (cruce(ch[pos], ch[x]) <= anterior[x]) x = ancestros[0][x]; ancestros[0][pos] = x; anterior[pos] = cruce(ch[pos], ch[x]); largo[pos] = largo[x] + 1; // ESTE ERA EL ERROR!!!! repa(i,1,18) { repa(i,lg[largo[pos]],1) { ancestros[i][pos] = ancestros[i-1][x]; x = ancestros[i][pos]; } for(auto h : hijos[pos]) { if (h.des == padre) continue; solve(h.des,pos,p+h.w); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //PRECALCULA EL LOGARITMO DE TODOS LOS VALORES lg[0] = lg[1] = 1; rep(i,2,MAX) lg[i] = ((1 << (lg[i - 1] + 1)) > i) ? lg[i - 1] : lg[i - 1] + 1; 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; largo[1] = 1; for (auto h : hijos[1]) { solve(h.des,1,h.w); } rep(i,2,n) cout << dp[i] << ' '; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...