#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
vector<pair<ll, ll>> e[100001];
struct Line {
ll m, b;
Line(ll m = 0, ll b = 0) : m(m), b(b) {}
/** Evaluates the linear function at position x */
ll operator()(ll x) { return m * x + b; }
/** Returns the x-coordinate of the intersection of two lines */
friend ld intersect(Line l1, Line l2) {
return (ld)(l2.b - l1.b) / (ld)(l1.m - l2.m);
}
};
Line stk[100001]; // convex hull of lines
int stk_max = 0;
ll h[100001], w[100001], dp[100001], s[100001], v[100001];
bool visited[100001];
ll line_min(ll x) {
// binary search for min value
int l = 0, r = stk_max - 1;
while (l < r) {
int m = (l + r) / 2;
if (intersect(stk[m], stk[m + 1]) < x) {
l = m + 1;
} else {
r = m;
}
}
return stk[l](x);
}
ll remove_pos(Line line) {
// check if hull is trivial or if line belongs at the end
if (stk_max < 2 || intersect(line, stk[stk_max - 1]) >=
intersect(stk[stk_max - 1], stk[stk_max - 2])) {
return stk_max;
}
// begin at l = 1 because we need to check intersection between k and k - 1
int l = 1, r = stk_max - 1;
while (l < r) {
int m = (l + r) / 2;
if (intersect(line, stk[m]) < intersect(stk[m], stk[m - 1])) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
// void calc_dist(int u){
// for (auto next : e[u]){
// if (!visited[next.first]){
// d[next.first] = d[u] + next.second;
// visited[next.first] = 1;
// calc_dist(next.first);
// }
// }
// return;
// }
void dfs(int u, int p, int d){
int prev_max, prev_pos;
Line prev_line;
if (u == 1) {
dp[u] = 0;
stk[stk_max++] = {0, 0};
}
else {
dp[u] = line_min(v[u]) + d * v[u] +
s[u];
Line l(
-d,
dp[u]);
prev_max = stk_max;
prev_pos = stk_max =
remove_pos(l);
prev_line =
stk[stk_max];
stk[stk_max++] = l;
}
for (auto [nex, w] : e[u]) {
if (nex != p) { dfs(nex, u, d + w); }
}
if (u != 1) {
stk_max = prev_max;
stk[prev_pos] = prev_line;
}
return;
}
int main() {
// freopen( "Harbingers.in", "r", stdin);
// freopen( "Harbingers.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 2; i <= n; i++){
int f, t, w;
cin >> f >> t >> w;
e[f].emplace_back(t,w);
e[t].emplace_back(f,w);
};
for (int i = 2; i <= n; i++) {
cin >> s[i] >> v[i];
}
dfs(1, 0, 0);
for (int i = 2; i <= n; i++) { cout << dp[i] << ' '; }
cout << '\n';
}
Compilation message
harbingers.cpp: In function 'void dfs(int, int, int)':
harbingers.cpp:94:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
94 | for (auto [nex, w] : e[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
33 ms |
15184 KB |
Output is correct |
| 4 |
Correct |
50 ms |
18660 KB |
Output is correct |
| 5 |
Correct |
56 ms |
21948 KB |
Output is correct |
| 6 |
Correct |
68 ms |
25176 KB |
Output is correct |
| 7 |
Correct |
38 ms |
15184 KB |
Output is correct |
| 8 |
Correct |
85 ms |
19212 KB |
Output is correct |
| 9 |
Correct |
84 ms |
20928 KB |
Output is correct |
| 10 |
Correct |
74 ms |
19652 KB |
Output is correct |
