#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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
2 |
Incorrect |
4 ms |
3540 KB |
Output isn't correct |
3 |
Incorrect |
49 ms |
11608 KB |
Output isn't correct |
4 |
Incorrect |
66 ms |
15868 KB |
Output isn't correct |
5 |
Incorrect |
75 ms |
17492 KB |
Output isn't correct |
6 |
Incorrect |
117 ms |
20716 KB |
Output isn't correct |
7 |
Incorrect |
63 ms |
12712 KB |
Output isn't correct |
8 |
Incorrect |
124 ms |
21632 KB |
Output isn't correct |
9 |
Incorrect |
132 ms |
22864 KB |
Output isn't correct |
10 |
Incorrect |
104 ms |
22232 KB |
Output isn't correct |