Submission #1214032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214032		trinm01	Harbingers (CEOI09_harbingers)	C++20	70 / 100	1096 ms	13636 KiB

harbingers

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

#define int long long
const int MAXN = 100000 + 5;
const int MAXE = 200000 + 5;
const int INF = 1e18;

int n;
int s[MAXN], p[MAXN], d[MAXN], f[MAXN];

// Adjacency as static edge list
int head[MAXN], to[MAXE], cost[MAXE], nxt[MAXE], ecnt;

// A, B arrays for CHT
int Aarr[MAXN], Barr[MAXN], asz = 0;

// Pop‐stack arrays
int popAarr[MAXN], popBarr[MAXN], popSz = 0;
// Number of pops performed when adding at node u
int popRange[MAXN];

void addEdge(int u, int v, int c) {
    nxt[ecnt] = head[u];
    to[ecnt] = v;
    cost[ecnt] = c;
    head[u] = ecnt++;
}

bool bad(int l1, int l2, int l3) {
    // compare (B[l3]-B[l1])*(A[l1]-A[l2]) < (B[l2]-B[l1])*(A[l1]-A[l3])
    long double lhs = (long double)(Barr[l3] - Barr[l1]) * (Aarr[l1] - Aarr[l2]);
    long double rhs = (long double)(Barr[l2] - Barr[l1]) * (Aarr[l1] - Aarr[l3]);
    return lhs < rhs;
}

void addLine(int a, int b, int u) {
    popRange[u] = 0;
    Aarr[asz] = a;
    Barr[asz] = b;
    asz++;
    while (asz >= 3 && bad(asz - 3, asz - 2, asz - 1)) {
        // pop the middle line
        int idx = asz - 2;
        popAarr[popSz] = Aarr[idx];
        popBarr[popSz] = Barr[idx];
        popSz++;
        // remove it: shift elements left at idx
        for (int i = idx; i + 1 < asz; i++) {
            Aarr[i] = Aarr[i + 1];
            Barr[i] = Barr[i + 1];
        }
        asz--;
        popRange[u]++;
    }
}

void rollback(int u) {
    // remove the line added for u
    asz--;
    // restore popped lines in reverse order
    for (int i = 0; i < popRange[u]; i++) {
        popSz--;
        // append restored line to end
        Aarr[asz] = popAarr[popSz];
        Barr[asz] = popBarr[popSz];
        asz++;
    }
}

int queryCHT(int x) {
    if (asz == 0) return 0;
    if (asz == 1) return Aarr[0] * x + Barr[0];
    int l = 1, r = asz - 1, id = 1;
    int ans = INF;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int y1 = Aarr[mid] * x + Barr[mid];
        int y2 = Aarr[mid - 1] * x + Barr[mid - 1];
        if (y1 < y2) {
            id = mid;
            ans = min(ans, y1);
            l = mid + 1;
        } else {
            ans = min(ans, y2);
            r = mid - 1;
        }
    }
    ans = min(ans, Aarr[id] * x + Barr[id]);
    if (id - 1 >= 0) ans = min(ans, Aarr[id - 1] * x + Barr[id - 1]);
    if (id + 1 < asz) ans = min(ans, Aarr[id + 1] * x + Barr[id + 1]);
    return ans;
}

void dfs_iterative() {
    struct Item { int u, par, state; };
    vector<Item> st;
    st.reserve(n * 2);
    d[1] = 0;
    st.push_back({1, 0, 0});
    while (!st.empty()) {
        Item it = st.back();
        st.pop_back();
        int u = it.u, par = it.par, state = it.state;
        if (state == 0) {
            if (u != 1) {
                int best = queryCHT(p[u]);
                f[u] = best + d[u] * p[u] + s[u];
            } else {
                f[u] = 0;
            }
            addLine(-d[u], f[u], u);
            st.push_back({u, par, 1});
            for (int e = head[u]; e != -1; e = nxt[e]) {
                int v = to[e], c = cost[e];
                if (v == par) continue;
                d[v] = d[u] + c;
                st.push_back({v, u, 0});
            }
        } else {
            rollback(u);
        }
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        head[i] = -1;
    }
    ecnt = 0;
    for (int i = 1; i < n; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        addEdge(u, v, c);
        addEdge(v, u, c);
    }
    for (int i = 2; i <= n; i++) {
        cin >> s[i] >> p[i];
    }
    asz = 0;
    popSz = 0;
    dfs_iterative();
    for (int i = 2; i <= n; i++) {
        cout << f[i] << ' ';
    }
    cout << "\n";
    return 0;
}

• Subtask 1: 70 / 100