# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
400180 | hltk | Harbingers (CEOI09_harbingers) | C++17 | 1097 ms | 19884 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 <bits/stdc++.h>
using namespace std;
// template <typename T>
// int bins(int l, int r, T f) {
// while (l < r) {
// int m = (l + r) / 2;
// f(m) ? r = m : l = m + 1;
// }
// return l;
// }
const long INF = 1e18;
int n, s[100100], t[100100];
long dp[100100];
vector<pair<int, int>> g[100100];
struct Line {
long m, c;
long operator()(long x) { return m * x + c; }
} cht[100100];
long intersect(Line a, Line b) {
long num = b.c - a.c, dem = a.m - b.m;
return num / dem - ((num ^ dem) < 0 && num % dem);
}
void dfs(int u, int p, int ed, long cd) {
if (u != 1) {
long r = -INF;
for (int i = 0; i < ed; ++i) r = max(r, cht[i](t[u]));
dp[u] = cd * t[u] + s[u] - r /* cht[bins(0, ed - 1, [&](int m) {
return cht[m](t[u]) > cht[m + 1](t[u]);
})](t[u])*/;
Line l{cd, -dp[u]};
int ned = 0;
while (ned + 1 < ed) {
if (intersect(cht[ned], cht[ned + 1]) < intersect(cht[ned + 1], l)) {
ned++;
} else break;
}
ned++;
swap(cht[ned], l);
// bins(0, ed - 1, [&](int m) {
// return intersect(cht[m], cht[m + 1]) >= intersect(cht[m + 1], l);
// });
for (auto [v, d] : g[u]) {
if (v == p) continue;
dfs(v, u, ned + 1, cd + d);
}
swap(cht[ned], l);
} else {
for (auto [v, d] : g[u]) {
if (v == p) continue;
dfs(v, u, ed, cd + d);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1, u, v, d; i <= n - 1; ++i) {
scanf("%d %d %d", &u, &v, &d);
g[u].emplace_back(v, d);
g[v].emplace_back(u, d);
}
for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i);
dfs(1, -1, 1, 0);
for (int i = 2; i <= n; ++i) printf("%ld%c", dp[i], i == n ? '\n' : ' ');
}
// f_j(x) := -dp[j] + dep[j] * x
// dp[j] + (d - x) t_i + s_i
// = dp[j] - x * t_i + d * t_i + s_i
// = -f_j(t_i) + d * t_i + s_i
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |