Submission #970469

#	Time	Username	Problem	Language	Result	Execution time	Memory
970469		vjudge1	Harbingers (CEOI09_harbingers)	C++17	100 / 100	91 ms	21636 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = int(1e5) + 5;

using ll = int64_t;

const ll INF = LLONG_MAX / 2;

struct line {
    ll a, b;

    ll eval(ll x) {
        return ll(1) * a * x + b;
    }

    ll div(ll a, ll b) const {
        return a / b - ((a ^ b) < 0 && a % b);
    }

    ll intersect(const line &oth) const {
        if (a == oth.a) {
            return b <= oth.b ? -INF : INF;
        }
        return div(b - oth.b, oth.a - a);
    }
};

int n, m;
int S[N], V[N];
ll dp[N], h[N];
line cht[N];
vector<pair<int, int>> g[N];
stack<pair<int, line>> his;

ll qry(ll x) {
    int l = 1, r = m - 1, ans = 1;
    while (l <= r) {
        int md = (l + r) / 2;
        if (cht[md].intersect(cht[md + 1]) < x) {
            l = md + 1;
            ans = md + 1;
        } else {
            r = md - 1;
        }
    }
    return cht[ans].eval(x);
}

void add(ll a, ll b) {
    int l = 1, r = m - 1, ans = m + 1;
    line x = {a, b};
    while (l <= r) {
        int md = (l + r) / 2;
        if (cht[md].intersect(cht[md + 1]) >= cht[md + 1].intersect(x)) {
            ans = md + 1;
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    his.emplace(m, cht[ans]);
    cht[ans] = x;
    m = ans;
}

void dfs(int u, int p) {
    if (u > 1) {
        dp[u] = -qry(V[u]) + S[u] + h[u] * V[u];
        add(h[u], -dp[u]);
    }
    for (auto [v, w] : g[u]) {
        if (v ^ p) {
            h[v] = h[u] + w;
            dfs(v, u);
        }
    }
    if (u > 1) {
        cht[m] = his.top().second;
        m = his.top().first;
        his.pop();
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    for (int i = 2; i <= n; ++i) {
        cin >> S[i] >> V[i];
    }
    m = 1;
    cht[1] = {0, 0};
    dfs(1, 1);
    for (int i = 2; i <= n; ++i) {
        cout << dp[i] << " ";
    }
}

• Subtask 1: 100 / 100