Submission #1263369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263369		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	50 / 100	54 ms	13404 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INFLL = (1LL<<62);

// Line: y = m*x + b
struct Line {
    ll m, b;
    long double xLeft; // from which x this line becomes best
    Line(ll _m=0, ll _b=INFLL, long double _x = -1e300L) : m(_m), b(_b), xLeft(_x) {}
    // safe evaluation using __int128
    ll eval(ll x) const {
        __int128 v = (__int128)m * (__int128)x + (__int128)b;
        if (v > (__int128)INFLL) return INFLL;
        if (v < -(__int128)INFLL) return -INFLL;
        return (ll)v;
    }
};

// Monotonic CHT for minimum queries with strictly decreasing slopes
struct MonotonicCHT {
    vector<Line> hull;
    // compute x-coordinate of intersection of l1 and l2
    static long double intersectX(const Line &l1, const Line &l2) {
        // (b2 - b1) / (m1 - m2)
        // m1 != m2 guaranteed
        long double num = (long double)(l2.b - l1.b);
        long double den = (long double)(l1.m - l2.m);
        return num / den;
    }

    void clear() { hull.clear(); }

    // Insert line with slope strictly decreasing
    void add_line(ll m, ll b) {
        Line nl(m,b,-1e300L);
        if (hull.empty()) {
            nl.xLeft = -1e300L;
            hull.push_back(nl);
            return;
        }
        // pop while new line makes last line irrelevant
        while (!hull.empty()) {
            long double x = intersectX(hull.back(), nl);
            if (x <= hull.back().xLeft) {
                hull.pop_back();
            } else {
                nl.xLeft = x;
                break;
            }
        }
        if (hull.empty()) nl.xLeft = -1e300L;
        hull.push_back(nl);
    }

    // pop lines back to size sz
    void rollback_to_size(int sz) {
        if ((int)hull.size() > sz) hull.resize(sz);
    }

    // query min at x
    ll query(ll x) const {
        if (hull.empty()) return INFLL;
        // find rightmost line with xLeft <= x
        int l = 0, r = (int)hull.size() - 1, ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (hull[mid].xLeft <= (long double)x) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        return hull[ans].eval(x);
    }
};

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,d; cin >> u >> v >> d;
        --u; --v;
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    vector<ll> S(N,0), V(N,0);
    for (int i = 1; i < N; ++i) cin >> S[i] >> V[i];

    // compute dist[] and parent[] using iterative BFS/DFS (root = 0)
    vector<ll> dist(N,0);
    vector<int> parent(N, -1), order;
    order.reserve(N);
    parent[0] = -2;
    order.push_back(0);
    for (size_t i = 0; i < order.size(); ++i) {
        int u = order[i];
        for (auto [v,w] : adj[u]) if (parent[v] == -1) {
                parent[v] = u;
                dist[v] = dist[u] + w;
                order.push_back(v);
            }
    }

    vector<ll> dp(N,0);
    MonotonicCHT cht;
    // iterative DFS stack of frames: (node, parent, next-child-index, state)
    // state 0 = entry not processed, state 1 = exit (rollback)
    struct Frame { int u, p; int it; bool entered; };
    vector<Frame> stk;
    stk.push_back({0, -1, 0, false});

    while (!stk.empty()) {
        Frame fr = stk.back(); stk.pop_back();
        int u = fr.u, p = fr.p;
        if (!fr.entered) {
            // ENTRY
            // compute dp
            if (u == 0) dp[u] = 0;
            else {
                ll best = cht.query(V[u]);
                // best should exist because root line is inserted before any children queries
                dp[u] = best;
                if (dp[u] >= INFLL/4) dp[u] = INFLL;
                else dp[u] = dp[u] + dist[u] * V[u] + S[u];
            }
            // record hull size for rollback
            int prevSize = (int)cht.hull.size();
            // push EXIT frame with prevSize encoded in it field
            stk.push_back({u, p, prevSize, true});

            // insert this node's line: slope = -dist[u], intercept = dp[u]
            cht.add_line(-dist[u], dp[u]);

            // push children for entry
            for (auto &ed : adj[u]) {
                int v = ed.first;
                if (v == p) continue;
                stk.push_back({v, u, 0, false});
            }
        } else {
            // EXIT: rollback hull to previous size stored in it
            cht.rollback_to_size(fr.it);
        }
    }

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

• Subtask 1: 50 / 100