Submission #1269656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269656		i_elhdad	Harbingers (CEOI09_harbingers)	C++20	70 / 100	130 ms	37384 KiB

harbingers

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

const ll NINF = LLONG_MIN / 4;

struct Line {
    ll a, b;
    Line(ll _a = 0, ll _b = NINF) : a(_a), b(_b) {}
};

struct Node {
    int l = -1, r = -1; // children indices in pool
    ll a = 0, b = NINF; // line: a * x + b
    Node() = default;
    Node(ll _a, ll _b) : l(-1), r(-1), a(_a), b(_b) {}
};

struct Change {
    // either pointer-change (isPtr=true) -> *where should be restored to oldPtr
    // or line-change (isPtr=false) -> pool[nodeIdx].(a,b) should be restored to oldLine
    bool isPtr;
    int *where; // address of int (root or pool[idx].l or pool[idx].r)
    int oldPtr;

    int nodeIdx;
    Line oldLine;
    Change(int* _where, int _oldPtr) : isPtr(true), where(_where), oldPtr(_oldPtr), nodeIdx(-1), oldLine() {}
    Change(int _nodeIdx, Line _oldLine) : isPtr(false), where(nullptr), oldPtr(-1), nodeIdx(_nodeIdx), oldLine(_oldLine) {}
};

vector<Change> changes;
vector<Node> pool; // node pool
vector<ll> xs;     // compressed x values (unique speeds)

inline size_t snapshot() { return changes.size(); }

inline void rollback(size_t snap, size_t pool_size_snap) {
    // restore line changes and pointer changes
    while (changes.size() > snap) {
        Change c = changes.back();
        changes.pop_back();
        if (c.isPtr) {
            *c.where = c.oldPtr;
        } else {
            pool[c.nodeIdx].a = c.oldLine.a;
            pool[c.nodeIdx].b = c.oldLine.b;
        }
    }
    // shrink pool back (discard nodes created after snapshot)
    while (pool.size() > pool_size_snap) pool.pop_back();
}

int newNode(Line ln) {
    pool.emplace_back(ln.a, ln.b);
    return int(pool.size()) - 1;
}

inline ll evalLine(const Line &ln, ll x) {
    return ln.a * x + ln.b;
}
inline ll evalNode(int idx, ll x) {
    return pool[idx].a * x + pool[idx].b;
}

// insert into Li-Chao over indices [L,R] (indexes into xs)
void insert_line(int &cur, Line line, int L, int R) {
    if (cur == -1) {
        // record the pointer change (cur was -1)
        changes.emplace_back(&cur, cur);
        cur = newNode(line);
        return;
    }
    if (pool[cur].a == line.a) {
        // only possibly update b (we maintain max)
        changes.emplace_back(cur, Line(pool[cur].a, pool[cur].b));
        pool[cur].b = max(pool[cur].b, line.b);
        return;
    }

    int mid = (L + R) >> 1;
    ll xmid = xs[mid];
    ll curMid = evalNode(cur, xmid);
    ll newMid = evalLine(line, xmid);

    if (newMid > curMid) {
        changes.emplace_back(cur, Line(pool[cur].a, pool[cur].b));
        // swap lines: keep best in node
        swap(pool[cur].a, line.a);
        swap(pool[cur].b, line.b);
    }
    if (L == R) return;

    ll xl = xs[L], xr = xs[R];
    ll curL = evalNode(cur, xl);
    ll newL = evalLine(line, xl);
    if (newL > curL) {
        insert_line(pool[cur].l, line, L, mid);
        return;
    }
    ll curR = evalNode(cur, xr);
    ll newR = evalLine(line, xr);
    if (newR > curR) {
        insert_line(pool[cur].r, line, mid + 1, R);
    }
}

ll query_idx(int idxX, int cur, int L, int R) {
    if (cur == -1) return NINF;
    ll res = evalNode(cur, xs[idxX]);
    if (L == R) return res;
    int mid = (L + R) >> 1;
    if (idxX <= mid) {
        return max(res, query_idx(idxX, pool[cur].l, L, mid));
    } else {
        return max(res, query_idx(idxX, pool[cur].r, mid + 1, R));
    }
}

// ---------------- main solution ----------------

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

    int n;
    if (!(cin >> n)) return 0;
    vector<vector<pair<int,int>>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w; cin >> u >> v >> w; --u; --v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<ll> S(n, 0), V(n, 0);
    for (int i = 1; i < n; ++i) {
        cin >> S[i] >> V[i];
    }

    // prepare compressed xs from speeds V[1..n-1]
    xs.clear();
    xs.reserve(n);
    for (int i = 1; i < n; ++i) xs.push_back(V[i]);
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    if (xs.size() == 0) {
        // degenerate (shouldn't happen since n>=3), but guard
        xs.push_back(1);
    } else if (xs.size() == 1) {
        // avoid single-point domain; add one sentinel
        xs.push_back(xs[0] + 1);
    }
    int m = int(xs.size());

    // reserve pool to avoid relocation (keeps addresses stable)
    pool.clear();
    pool.reserve(4 * m + 5); // heuristic, reduces reallocations
    changes.clear();

    int root = -1;
    vector<ll> dp(n, 0);

    // DFS with rollback
    // compute dist (distance from root) along recursion
    function<void(int,int,ll)> dfs = [&](int u, int p, ll dist) {
        size_t snap = snapshot();
        size_t pool_snap = pool.size();

        if (u == 0) {
            dp[u] = 0;
        } else {
            // find index of V[u] in xs
            int idx = int(lower_bound(xs.begin(), xs.end(), V[u]) - xs.begin());
            ll best = query_idx(idx, root, 0, m - 1); // returns max(dist_x * V[u] - dp_x)
            dp[u] = S[u] + V[u] * dist - best;
        }
        // insert this node's line for descendants: line = { dist, -dp[u] }
        insert_line(root, Line(dist, -dp[u]), 0, m - 1);

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

        rollback(snap, pool_snap);
    };

    dfs(0, -1, 0);

    for (int i = 1; i < n; ++i) {
        cout << dp[i] << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

• Subtask 1: 70 / 100