Submission #1263074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263074		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	20 / 100	152 ms	131072 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;
const ll X_MIN = 0;
const ll X_MAX = 1000000000LL; // V_i up to 1e9

struct Line {
    ll m, b; // y = m*x + b
    bool empty;
    Line(): m(0), b(0), empty(true) {}
    Line(ll _m, ll _b): m(_m), b(_b), empty(false) {}
    ll eval(ll x) const { return empty ? INF : m * x + b; }
};

struct Node {
    Line ln;
    int l = 0, r = 0;
    Node(): ln(), l(0), r(0) {}
};

struct LiChaoRollback {
    vector<Node> nodes;            // 1-based nodes, nodes[0] unused
    vector<int> created;           // indices of nodes created (for rollback)
    vector<pair<int, Node>> mods;  // saved previous node states (idx, oldNode)

    LiChaoRollback() { nodes.emplace_back(); } // index 0 unused

    int create_node() {
        nodes.emplace_back();
        int idx = (int)nodes.size() - 1;
        created.push_back(idx);
        return idx;
    }

    void backup_node(int idx) {
        mods.emplace_back(idx, nodes[idx]);
    }

    void insert(Line nw, int idx, ll l = X_MIN, ll r = X_MAX) {
        if (idx == 0) {
            // shouldn't happen: we always create node before recursing
            idx = create_node();
        }
        if (nodes[idx].ln.empty) {
            backup_node(idx);
            nodes[idx].ln = nw;
            return;
        }
        ll mid = (l + r) >> 1;
        // If new is better at mid, swap (store old)
        if (nw.eval(mid) < nodes[idx].ln.eval(mid)) {
            backup_node(idx);
            swap(nodes[idx].ln, nw);
        }
        if (l == r) return;
        if (nw.eval(l) < nodes[idx].ln.eval(l)) {
            // go left
            if (nodes[idx].l == 0) {
                backup_node(idx);
                nodes[idx].l = create_node();
            }
            insert(nw, nodes[idx].l, l, mid);
        } else {
            // go right
            if (nodes[idx].r == 0) {
                backup_node(idx);
                nodes[idx].r = create_node();
            }
            insert(nw, nodes[idx].r, mid + 1, r);
        }
    }

    ll query(ll x, int idx, ll l = X_MIN, ll r = X_MAX) const {
        if (idx == 0) return INF;
        ll res = nodes[idx].ln.eval(x);
        if (l == r) return res;
        ll mid = (l + r) >> 1;
        if (x <= mid) {
            if (nodes[idx].l == 0) return res;
            return min(res, query(x, nodes[idx].l, l, mid));
        } else {
            if (nodes[idx].r == 0) return res;
            return min(res, query(x, nodes[idx].r, mid + 1, r));
        }
    }

    // wrappers using root index 1
    int root() {
        if ((int)nodes.size() <= 1) create_node(); // ensure root exists
        return 1;
    }

    pair<int,int> snapshot() const {
        return { (int)created.size(), (int)mods.size() };
    }

    void rollback(pair<int,int> snap) {
        int targetCreated = snap.first;
        int targetMods = snap.second;
        // revert modifications
        while ((int)mods.size() > targetMods) {
            auto pr = mods.back(); mods.pop_back();
            int idx = pr.first;
            nodes[idx] = pr.second;
        }
        // remove newly created nodes
        while ((int)created.size() > targetCreated) {
            int idx = created.back(); created.pop_back();
            // drop last node (must be at position idx)
            // nodes vector may be larger; safe to pop_back
            nodes.pop_back();
        }
        // note: parent pointers were restored by reverting mods
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if defined(__linux__)
    // no-op
#endif

    int N;
    if (!(cin >> N)) return 0;
    vector<vector<pair<int,int>>> g(N+1);
    for (int i = 0; i < N-1; ++i) {
        int u,v,d; cin >> u >> v >> d;
        g[u].push_back({v,d});
        g[v].push_back({u,d});
    }
    // read harbingers for towns 2..N
    vector<ll> S(N+1,0), V(N+1,0);
    for (int i = 2; i <= N; ++i) {
        cin >> S[i] >> V[i];
    }
    // compute dist from root (1)
    vector<ll> dist(N+1,0);
    {
        vector<int> st; st.reserve(N);
        st.push_back(1);
        vector<int> parent(N+1, -1);
        parent[1] = 0;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            for (auto [v,w] : g[u]) if (v != parent[u]) {
                parent[v] = u;
                dist[v] = dist[u] + w;
                st.push_back(v);
            }
        }
    }

    // dp[1] = 0
    vector<ll> dp(N+1, 0);
    LiChaoRollback lichao;
    // ensure root node index 1 exists
    if ((int)lichao.nodes.size() <= 1) lichao.create_node();
    int rootIdx = 1;
    // insert line for root: m = -dist[1] = 0, b = dp[1] = 0
    lichao.insert(Line(-dist[1], dp[1]), rootIdx);

    // do DFS from root using recursion with rollback
    // recursion depth up to N; acceptable for typical judges
    function<void(int,int)> dfs = [&](int u, int p) {
        for (auto [v,w]: g[u]) if (v != p) {
            // query using current hull (contains ancestors including u)
            ll best = lichao.query(V[v], rootIdx);
            dp[v] = S[v] + V[v] * dist[v] + best;
            // add line for v and recurse
            auto snap = lichao.snapshot();
            lichao.insert(Line(-dist[v], dp[v]), rootIdx);
            dfs(v, u);
            lichao.rollback(snap);
        }
    };

    dfs(1, 0);

    // output dp[2..N]
    for (int i = 2; i <= N; ++i) {
        if (i > 2) cout << ' ';
        cout << dp[i];
    }
    cout << '\n';
    return 0;
}

• Subtask 1: 20 / 100