Submission #1345628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345628		po_rag526	Harbingers (CEOI09_harbingers)	C++20	100 / 100	69 ms	25284 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define endl "\n"

const ll inf = 2e18;

template<bool IS_MAX = false, bool IS_INC = false>
struct RollbackCHT {
    struct Line {
        ll m, c;
        Line() : m(0), c(inf) {}
        Line(ll m, ll c) : m(m), c(c) {}
        ll eval(ll x) const { return m * x + c; }
    };

    struct History {
        int pos;
        int sz;
        Line old_line;
    };

    vector<Line> st;
    vector<History> hist;
    int sz;

    RollbackCHT(int max_nodes) {
        st.resize(max_nodes);
        hist.reserve(max_nodes);
        sz = 0;
    }

    bool redundant(Line l1, Line l2, Line l3) {
        __int128 dx1 = l1.m - l2.m;
        __int128 dc1 = l2.c - l1.c;
        __int128 dx2 = l2.m - l3.m;
        __int128 dc2 = l3.c - l2.c;
        return dc1 * dx2 >= dc2 * dx1;
    }

    void add(ll m, ll c) {
        ll m_int = IS_INC ? -m : m;
        ll c_int = IS_MAX ? -c : c;

        Line l_new(m_int, c_int);
        int pos = sz;
        int low = 1, high = sz - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            if (redundant(st[mid - 1], st[mid], l_new)) {
                pos = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        hist.push_back({pos, sz, st[pos]});
        st[pos] = l_new;
        sz = pos + 1;
    }

    void rollback() {
        if (hist.empty()) return;
        auto h = hist.back();
        hist.pop_back();
        sz = h.sz;
        st[h.pos] = h.old_line;
    }

    ll query(ll x) {
        if (sz == 0) return IS_MAX ? -inf : inf;

        ll x_int = (IS_INC != IS_MAX) ? -x : x;

        int low = 0, high = sz - 2;
        int best = sz - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            if (st[mid].eval(x_int) <= st[mid + 1].eval(x_int)) {
                best = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        ll ans = st[best].eval(x_int);
        return IS_MAX ? -ans : ans;
    }
};

vector<vector<pair<int,int>>> adj;
vector<ll> wait_t, speed, ans;
RollbackCHT<false, false> cht(1e5);

void go(int u, int p, ll d) {
    if (u != 1) ans[u] = cht.query(speed[u]) + d * speed[u] + wait_t[u];
    cht.add(-d, ans[u]);

    for (auto [v, dist] : adj[u]) {
        if (v == p) continue;
        go(v, u, d + dist);
    }

    cht.rollback();
};

void solve() {
    int n;
    cin >> n;

    adj.assign(n + 1, {});
    wait_t.assign(n + 1, 0);
    speed.assign(n + 1, 0);
    ans.assign(n + 1, 0);

    for (int i = 1; i < n; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }

    for (int i = 2; i <= n; i++) cin >> wait_t[i] >> speed[i];

    go(1, 0, 0);

    for (int i = 2; i <= n; i++) cout << ans[i] << " ";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

• Subtask 1: 100 / 100