Submission #1214031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214031		trinm01	Harbingers (CEOI09_harbingers)	C++20	70 / 100	189 ms	131072 KiB

harbingers

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

#define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll INF = (ll)1e18;
const int MAXN = 100000 + 1;

int n, s[MAXN], p[MAXN], d[MAXN];
vector<pii> adj[MAXN];
int f[MAXN];
vector<int> A, B, xoaA[MAXN], xoaB[MAXN];

bool bad(int l1, int l2, int l3) {
    int lhs = (int)(B[l3] - B[l1]) * (A[l1] - A[l2]);
    int rhs = (int)(B[l2] - B[l1]) * (A[l1] - A[l3]);
    return lhs < rhs;
}

void add(int a, int b, int u) {
    A.push_back(a);
    B.push_back(b);
    while ((int)A.size() >= 3 && bad(A.size() - 3, A.size() - 2, A.size() - 1)) {
        int m = A.size();
        xoaA[u].push_back(A[m - 2]);
        xoaB[u].push_back(B[m - 2]);
        A.erase(A.end() - 2);
        B.erase(B.end() - 2);
    }
}

void hoi(int u) {
    A.pop_back();
    B.pop_back();
    FOD(i, (int)xoaA[u].size() - 1, 0) {
        A.push_back(xoaA[u][i]);
        B.push_back(xoaB[u][i]);
    }
    xoaA[u].clear();
    xoaB[u].clear();
}

int queryCHT(int x) {
    int sz = A.size();
    if (sz == 0) return 0;
    if (sz == 1) return A[0] * x + B[0];
    int l = 1, r = sz - 1, id = 1;
    int ans = INF;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int y1 = A[mid] * x + B[mid];
        int y2 = A[mid - 1] * x + B[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, A[id] * x + B[id]);
    if (id - 1 >= 0) ans = min(ans, A[id - 1] * x + B[id - 1]);
    if (id + 1 < sz) ans = min(ans, A[id + 1] * x + B[id + 1]);
    return ans;
}

void dfs2() {
    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;
            }
            add(-d[u], f[u], u);
            st.push_back({u, par, 1});
            for (int i = adj[u].size() - 1; i >= 0; i--) {
                int v = adj[u][i].fi, c = adj[u][i].se;
                if (v == par) continue;
                d[v] = d[u] + c;
                st.push_back({v, u, 0});
            }
        } else {
            hoi(u);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    FOR(i, 1, n) {
        adj[i].clear();
        xoaA[i].clear();
        xoaB[i].clear();
    }
    FOR(i, 1, n - 1) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    FOR(i, 2, n) {
        cin >> s[i] >> p[i];
    }
    A.clear();
    B.clear();
    dfs2();
    FOR(i, 2, n) {
        cout << f[i] << ' ';
    }
    cout << "\n";
    return 0;
}

• Subtask 1: 70 / 100