Submission #1216599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216599		tin_le	Harbingers (CEOI09_harbingers)	C++20	100 / 100	64 ms	30536 KiB

harbingers

//Huyduocdithitp
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
#define endl '\n'
#define pii pair<ll,ll>
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

static const ll INF = (ll)1e18;
const int N = 100005;

ll n;
ll d[N], F[N], S[N], V[N];
vector<pii> adj[N];

struct Undo_CHT {
    struct Line { ll a, b; };
    struct UndoEntry {
        Line prev;
        ll pos, old_sz;
    };

    vector<Line> A;
    vector<UndoEntry> undo;
    ll sz = 0;

    Undo_CHT() {
        A.resize(200005);
        undo.reserve(200005);
    }

    static bool bad(const Line &l1, const Line &l2, const Line &l3) {
        return double(l3.b - l1.b) / (l1.a - l3.a)
             < double(l2.b - l1.b) / (l1.a - l2.a);
    }

    void add(ll u, ll v) {
        Line x = {u, v};
        ll l = 1, r = sz - 1, ans = sz;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (bad(A[mid-1], A[mid], x)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        // save old state
        undo.push_back({ A[ans], ans, sz });
        A[ans] = x;
        sz = ans + 1;
    }

    void Undo() {
        auto e = undo.back(); undo.pop_back();
        sz = e.old_sz;
        A[e.pos] = e.prev;
    }

    ll cal(const Line &L, ll x) const {
        return L.a * x + L.b;
    }

    ll qr(ll x) const {
        if (sz == 0) return 0;
        ll ans = cal(A[0], x);
        ll l = 1, r = sz - 1;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (cal(A[mid], x) < cal(A[mid-1], x)) {
                ans = min(ans, cal(A[mid], x));
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

Undo_CHT cht;

void dfs(int u, int parent) {
    if (u == 1) {
        cht.add(0, 0);
    } else {
        F[u] = cht.qr(V[u]) + S[u] + V[u] * d[u];
        cht.add(-d[u], F[u]);
    }

    for (auto &e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == parent) continue;
        d[v] = d[u] + w;
        dfs(v, u);
    }

    if (u != 1) {
        cht.Undo();
    }
}

signed main() {
    faster;
    cin >> n;
    for (int i = 1; i < n; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i = 2; i <= n; i++) {
        cin >> S[i] >> V[i];
    }

    dfs(1, 0);
    for (int i = 2; i <= n; i++) {
        cout << F[i] << " ";
    }
    cout << endl;
    return 0;
}

• Subtask 1: 100 / 100