Submission #1345612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345612		po_rag526	Harbingers (CEOI09_harbingers)	C++20	90 / 100	60 ms	34536 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define int long long
#define endl "\n"
//-------------------\\

const int inf = 2e18;
template<bool IS_MAX = false, bool IS_INC = false>
struct RollbackCHT {
    struct Line {
        int m, c;

        Line() : m(0), c(inf) {}

        Line(int m, int c) : m(m), c(c) {}

        int eval(int 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);
        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(int m, int c) {
        int m_int = IS_INC ? -m : m;
        int 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 - low) / 2;
            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;
        History h = hist.back();
        hist.pop_back();
        sz = h.sz;
        st[h.pos] = h.old_line;
    }

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

        int 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 - low) / 2;
            if (st[mid].eval(x_int) <= st[mid + 1].eval(x_int)) {
                best = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

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

void solve() {
    int n; cin >> n;
    vector<vector<array<int,2>>> adj(n+1);
    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});
    }
    int wait[n+1] = {}, speed[n+1] = {};
    for (int i = 2; i <= n; i++) cin >> wait[i] >> speed[i];

    ll ans[n+1] = {};
    RollbackCHT<false,false> cht(n);
    function<void(int,int,int)> go = [&](int u, int p, int d) {
        if (u != 1) ans[u] = cht.query(speed[u]) + d * speed[u] + wait[u];
        cht.add(-d,ans[u]);

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

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(9);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

• Subtask 1: 90 / 100