| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 491488 | blue | Harbingers (CEOI09_harbingers) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define pb push_back
const int maxN = 100'000;
const int lgN = 17;
ll INF = 2'000'000'001;
vector<pair<int, ll>> edge[1+maxN];
vll S(1+maxN), V(1+maxN);
vi P(1+maxN);
vll D(1+maxN, 0);
vi ord;
void dfs(int u, int p)
{
ord.push_back(u);
P[u] = p;
for(auto x: edge[u])
{
int v = x.first;
ll d = x.second;
if(v == p) continue;
D[v] = D[u] + d;
dfs(v, u);
}
}
struct line
{
ll a;
ll b;
ll eval(ll x)
{
return a*x + b;
}
};
bool intersect_comp(line A, line B, line C, line D)
{
//A.a * x + A.b == B.a * x + B.b, x = (B.b - A.b)/(A.a - B.a)
ll mul = 1;
if(A.a - B.a < 0) mul *= -1;
if(C.a - D.a < 0) mul *= -1;
return mul * (B.b - A.b) * (C.a - D.a) < mul * (D.b - C.b) * (A.a - B.a);
}
vector<line> cht(1+maxN);
int cht_anc[1+maxN][1+lgN];
void insert_line(int u, line l)
{
cht[u] = l;
int a = P[u];
for(int e = lgN; e >= 0; e--)
{
int v = cht_anc[a][e];
if(v == 1) continue;
int w = cht_anc[v][0];
if(!intersect_comp(cht[w], cht[v], cht[v], l))
a = w;
}
cht_anc[u][0] = a;
for(int e = 1; e <= lgN; e++)
cht_anc[u][e] = cht_anc[ cht_anc[u][e-1] ][e-1];
}
ll query(int u, ll x)
{
for(int e = lgN; e >= 0; e--)
{
int v = cht_anc[u][e];
if(v == 1) continue;
int w = cht_anc[v][0];
cerr << "query " << u << ' ' << x << " : " << "checking " << w << ", " << v << '\n';
ll mul = 1;
if(cht[w].a - cht[v].a < 0) mul = -1;
if(x * (cht[w].a - cht[v].a) * mul <= (cht[v].b - cht[w].b) * mul)
u = w;
}
return min({cht[u].eval(x), cht[P[u]].eval(x), cht[P[P[u]]].eval(x)});
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
for(int i = 1; i <= N-1; i++)
{
int u, v;
ll d;
cin >> u >> v >> d;
edge[u].pb({v, d});
edge[v].pb({u, d});
}
for(int i = 2; i <= N; i++) cin >> S[i] >> V[i];
dfs(1, 1);
for(int i = 1; i <= N; i++)
for(int e = 0; e <= lgN; e++)
cht_anc[i][e] = i;
insert_line(1, {0, 0});
vll dp(1+N, INF);
dp[1] = 0;
for(int u: ord)
{
if(u == 1) continue;
dp[u] = ll(S[u]) + ll(V[u])*ll(D[u]) + query(P[u], V[u]);
insert_line(u, {-D[u], dp[u]});
}
// cerr << cht_anc[1][0] << ' ' << cht_anc[2][0] << '\n';
for(int i = 2; i <= N; i++) cout << dp[i] << ' ';
cout << '\n';
}