#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 time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
3284 KB |
Output isn't correct |
| 3 |
Incorrect |
65 ms |
12276 KB |
Output isn't correct |
| 4 |
Incorrect |
92 ms |
17132 KB |
Output isn't correct |
| 5 |
Incorrect |
126 ms |
21916 KB |
Output isn't correct |
| 6 |
Incorrect |
160 ms |
26428 KB |
Output isn't correct |
| 7 |
Incorrect |
100 ms |
16288 KB |
Output isn't correct |
| 8 |
Incorrect |
155 ms |
22344 KB |
Output isn't correct |
| 9 |
Incorrect |
156 ms |
24016 KB |
Output isn't correct |
| 10 |
Incorrect |
149 ms |
23080 KB |
Output isn't correct |
