Submission #1263079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263079		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	70 / 100	99 ms	39076 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;

struct Line {
    ll m, 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; }
};

int N;
vector<vector<pair<int,int>>> g;
vector<ll> S, V, distv, dp;
vector<ll> xs;            // compressed unique V values
vector<Line> seg;         // segment tree of lines (size 4*M)
vector<pair<int, Line>> mods; // stack of modifications for rollback

// backup seg[idx] before overwriting
void save_mod(int idx) {
    mods.emplace_back(idx, seg[idx]);
}

// insert line into node id covering [l..r] (indices into xs)
void insert_line(Line nw, int id, int l, int r) {
    int mid = (l + r) >> 1;
    ll xl = xs[l], xm = xs[mid], xr = xs[r];
    if (seg[id].empty) {
        save_mod(id);
        seg[id] = nw;
        return;
    }
    // ensure seg[id] is better at xm
    if (nw.eval(xm) < seg[id].eval(xm)) {
        save_mod(id);
        swap(seg[id], nw);
    }
    if (l == r) return;
    // If new line is better at left endpoint, go left
    if (nw.eval(xl) < seg[id].eval(xl)) {
        insert_line(nw, id<<1, l, mid);
    }
    // else if new line is better at right endpoint, go right
    else if (nw.eval(xr) < seg[id].eval(xr)) {
        insert_line(nw, id<<1|1, mid+1, r);
    }
    // else nowhere dominated on this segment
}

ll query_x(ll xq, int id, int l, int r) {
    if (id >= (int)seg.size()) return INF;
    ll res = seg[id].eval(xq);
    if (l == r) return res;
    int mid = (l + r) >> 1;
    if (xq <= xs[mid]) return min(res, query_x(xq, id<<1, l, mid));
    else return min(res, query_x(xq, id<<1|1, mid+1, r));
}

pair<int,int> snapshot() {
    return { (int)mods.size(), 0 }; // second unused but kept similar to earlier API
}
void rollback(pair<int,int> snap) {
    int target = snap.first;
    while ((int)mods.size() > target) {
        auto pr = mods.back(); mods.pop_back();
        seg[pr.first] = pr.second;
    }
}

void dfs(int u, int p, int M) {
    for (auto [v, w] : g[u]) if (v != p) {
        // query current hull at V[v]
        ll best = query_x(V[v], 1, 0, M-1);
        dp[v] = S[v] + V[v] * distv[v] + best;
        // insert line for v: y(x) = dp[v] + (-dist[v]) * x
        auto snap = snapshot();
        insert_line(Line(-distv[v], dp[v]), 1, 0, M-1);
        dfs(v, u, M);
        rollback(snap);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N)) return 0;
    g.assign(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});
    }
    S.assign(N+1, 0);
    V.assign(N+1, 0);
    for (int i = 2; i <= N; ++i) cin >> S[i] >> V[i];

    // compute dist from root (1)
    distv.assign(N+1, 0);
    {
        vector<int> st; 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;
                distv[v] = distv[u] + w;
                st.push_back(v);
            }
        }
    }

    // compress V values (we only need to query at these)
    xs.clear();
    for (int i = 2; i <= N; ++i) xs.push_back(V[i]);
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int M = (int)xs.size();
    if (M == 0) return 0; // no queries, but N>=3 so shouldn't happen

    // prepare segment tree arrays; size 4*M is safe
    seg.assign(4*M + 5, Line());
    mods.clear();

    dp.assign(N+1, 0);
    // root line: dp[1] = 0, dist[1] = 0 => y = 0
    // insert root line before starting DFS
    insert_line(Line(-distv[1], dp[1]), 1, 0, M-1);
    dfs(1, 0, M);

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

• Subtask 1: 70 / 100