# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
973820 | duckindog | Harbingers (CEOI09_harbingers) | C++17 | 87 ms | 25172 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.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 1;
int n;
vector<pair<int, int>> ad[N];
int s[N], velocity[N];
int d[N];
struct Line {
long long a, b;
double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
};
struct CHT {
int top;
array<Line, N> hull;
array<pair<int, Line>, N> save;
void add(Line line, int u) {
int preTop = top;
int l = 2, r = top; top += 1;
while (l <= r) {
int mid = l + r >> 1;
if (hull[mid].x(hull[mid - 1]) >= hull[mid].x(line)) l = (top = mid) + 1;
else r = mid - 1;
}
save[u] = {preTop, hull[top]};
hull[top] = line;
}
long long query(int u) {
auto cal = [&](int it) {
return hull[it].a * velocity[u] + hull[it].b + 1ll * d[u] * velocity[u] + s[u];
};
int l = 1, r = top - 1, it = 1;
while (l <= r) {
int mid = l + r >> 1;
if (cal(mid) >= cal(mid + 1)) l = it = mid + 1;
else r = mid - 1;
}
return cal(it);
}
} convex;
long long dp[N];
void dfs(int u, int p = 0) {
auto& ret = dp[u];
ret = min(ret, convex.query(u));
convex.add({-d[u], ret}, u);
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
d[v] = d[u] + w;
dfs(v, u);
}
auto[top, line] = convex.save[u];
convex.hull[convex.top] = line;
convex.top = top;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 2; i <= n; ++i) {
int u, v, w; cin >> u >> v >> w;
ad[u].push_back({v, w});
ad[v].push_back({u, w});
}
for (int i = 2; i <= n; ++i) cin >> s[i] >> velocity[i];
memset(dp, 40, sizeof dp);
dfs(1);
for (int i = 2; i <= n; ++i) cout << dp[i] << " \n"[i == n];
cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |