#include <iostream>
#include <vector>
#include <deque>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pi = pair<int, int>;
using vpi = vector<pi>;
#define sz(x) ((int)x.size())
const int maxN = 100'000;
const int INF = 2'000'000'001;
vi S(1+maxN), V(1+maxN);
vi D(1+maxN, 0);
vi ord(1, 0);
vector<vpi> edge(1+maxN);
void dfs(int u, int p)
{
ord.push_back(u);
for(auto k: edge[u])
{
if(k.first == p) continue;
D[k.first] = D[u] + k.second;
dfs(k.first, 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;
vl dp(1+maxN, INF);
ll query(ll x)
{
int lo = 0;
int hi = sz(cht) - 1;
while(lo != hi)
{
int mid = (lo+hi)/2;
//if(x <= (cht[mid+1].b - cht[mid].b)/(cht[mid].a - cht[mid+1].a))
ll mul = 1;
if(cht[mid].a - cht[mid+1].a < 0) mul = -1;
if(x * (cht[mid].a - cht[mid+1].a) * mul <= (cht[mid+1].b - cht[mid].b) * mul)
hi = mid;
else
lo = mid+1;
}
return cht[lo].eval(x);
}
void insert_line(line x)
{
while(sz(cht) >= 2 && !intersect_comp(cht[sz(cht) - 2], cht[sz(cht) - 1], cht[sz(cht) - 1], x))
cht.pop_back();
cht.push_back(x);
}
int main()
{
int N;
cin >> N;
for(int i = 1; i <= N-1; i++)
{
int u, v, d;
cin >> u >> v >> d;
edge[u].push_back({v, d});
edge[v].push_back({u, d});
}
for(int i = 2; i <= N; i++) cin >> S[i] >> V[i];
dfs(1, 1);
insert_line({0, 0});
dp[1] = 0;
for(int f = 2; f <= N; f++)
{
int i = ord[f];
dp[i] = ll(S[i]) + ll(V[i])*ll(D[i]) + query(V[i]);
insert_line({-D[i], dp[i]});
}
for(int i = 2; i <= N; i++) cout << dp[i] << ' ';
cout << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4556 KB |
Output isn't correct |
2 |
Correct |
6 ms |
4812 KB |
Output is correct |
3 |
Correct |
75 ms |
8668 KB |
Output is correct |
4 |
Correct |
99 ms |
10684 KB |
Output is correct |
5 |
Correct |
136 ms |
12100 KB |
Output is correct |
6 |
Correct |
162 ms |
13656 KB |
Output is correct |
7 |
Incorrect |
106 ms |
9276 KB |
Output isn't correct |
8 |
Incorrect |
178 ms |
12112 KB |
Output isn't correct |
9 |
Incorrect |
163 ms |
12568 KB |
Output isn't correct |
10 |
Incorrect |
151 ms |
12784 KB |
Output isn't correct |