#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], d[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 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[u] * v[u] +
s[u];
Line l(
-d[u],
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); }
}
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];
}
calc_dist(1);
dfs(1, 0);
for (int i = 2; i <=n; i++){
cout<<dp[i]<<' ';
}
}
Compilation message
harbingers.cpp: In function 'void dfs(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]) {
| ^
harbingers.cpp: In function 'int main()':
harbingers.cpp:106:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | freopen( "Harbingers.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:107:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen( "Harbingers.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
6 ms |
9560 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
6 ms |
9820 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
7 ms |
9564 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
6 ms |
9564 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
6 ms |
9564 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
6 ms |
9620 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
6 ms |
9560 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
6 ms |
9564 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
6 ms |
9564 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
6 ms |
9560 KB |
Execution killed with signal 11 |
