Submission #319697

#	Time	Username	Problem	Language	Result	Execution time	Memory
319697		nhtrnm	Harbingers (CEOI09_harbingers)	C++17	100 / 100	150 ms	24036 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;

struct Line {
    ll k, m;
};

ll intersect_x(const Line &l1, const Line &l2) {
    ll a = l1.m - l2.m, b = l2.k - l1.k;
    return a / b + ((a ^ b) > 0 && a % b);
}

ll get_y(const Line &l, ll x) {
    return l.k * x + l.m;
}

const int N = 100005;
vector<pair<int, int>> g[N];
ll prep[N], vel[N], dp[N];
pair<Line, ll> hull[N];

void compute_dp(int u, int p = 0, ll total_d = 0, int hull_n = 0) {
    if (u != 1) {
        int l = 0, r = hull_n;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (hull[m].second <= vel[u]) {
                l = m;
            } else {
                r = m;
            }
        }
        dp[u] = get_y(hull[l].first, vel[u]) + total_d * vel[u] + prep[u];
    }
    Line next_line = {-total_d, dp[u]};
    int l = 0, r = hull_n;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (hull[m].second < intersect_x(hull[m].first, next_line)) {
            l = m;
        } else {
            r = m;
        }
    }
    auto last = hull[r];
    ll next_x = r == 0 ? LLONG_MIN : intersect_x(hull[r - 1].first, next_line);
    hull[r] = {next_line, next_x};
    for (auto [v, d] : g[u]) {
        if (v == p) {
            continue;
        }
        compute_dp(v, u, total_d + d, r + 1);
    }
    hull[r] = last;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(cout.fixed);
    cout.precision(20);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        g[u].emplace_back(v, d);
        g[v].emplace_back(u, d);
    }
    for (int i = 2; i <= n; i++) {
        cin >> prep[i] >> vel[i];
    }
    compute_dp(1);
    for (int i = 2; i <= n; i++) {
        cout << dp[i] << " ";
    }
    cout << "\n";
}

• Subtask 1: 100 / 100