Submission #1306259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306259		WeIlIaN	Harbingers (CEOI09_harbingers)	C++20	50 / 100	114 ms	25164 KiB

harbingers

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

#define fir first
#define sec second
#define pushb push_back
#define mp make_pair
#define FOR2(i, a) for (int i = 0; i < (a); ++i)
#define FOR3(i, a, b) for (int i = (a); i < (b); ++i)
#define overload3(a, b, c, d, ...) d
#define REP(...) overload3(__VA_ARGS__, FOR3, FOR2)(__VA_ARGS__)

using ll = long long;
using ld = long double;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vll = vector<ll>;

static const ll INF = (ll)4e18;
static const int MAXN = 200000 + 5; // adjust if needed (must be >= n)

struct Line {
    ll m, b;
    Line(ll m=0, ll b=0): m(m), b(b) {}
    ll eval(ll x) const {
        // avoid overflow if needed:
        __int128 v = (__int128)m * x + b;
        if (v > (__int128)LLONG_MAX) return LLONG_MAX;
        if (v < (__int128)LLONG_MIN) return LLONG_MIN;
        return (ll)v;
    }
};

// intersection x-coordinate of l1 and l2 (they must have different slopes)
static inline ld intersectX(const Line &l1, const Line &l2) {
    // l1.m != l2.m
    return (ld)(l2.b - l1.b) / (ld)(l1.m - l2.m);
}

// ---- CHT storage: fixed array like sample ----
static Line stk[MAXN];
static int stk_max = 0;

// query min at x (binary search on intersections)
static inline ll line_min(ll x) {
    int l = 0, r = stk_max - 1;
    while (l < r) {
        int m = (l + r) >> 1;
        if (intersectX(stk[m], stk[m + 1]) < (ld)x) l = m + 1;
        else r = m;
    }
    return stk[l].eval(x);
}

// find position where new line should be placed, and hull after that is removed
static inline int remove_pos(const Line &line) {
    if (stk_max < 2) return stk_max;

    // if line belongs at the end (no removals)
    if (intersectX(line, stk[stk_max - 1]) >= intersectX(stk[stk_max - 1], stk[stk_max - 2]))
        return stk_max;

    // binary search for first position to replace
    int l = 1, r = stk_max - 1;
    while (l < r) {
        int m = (l + r) >> 1;
        if (intersectX(line, stk[m]) < intersectX(stk[m], stk[m - 1])) r = m;
        else l = m + 1;
    }
    return l;
}

// ---- Tree DP ----
vvpll adj;
vll ans;
vpll har;

void dfs(int u, int p = -1, ll d = 0) {
    int prev_max = stk_max;
    int prev_pos = -1;
    Line prev_line;

    if (u == 0) {
        ans[u] = 0;
        stk[stk_max++] = Line(0, 0);
    } else {
        auto [s, t] = har[u];

        ll best = line_min(t);
        __int128 val = (__int128)best + s + (__int128)t * d;
        ans[u] = (ll)val;

        Line nl(-d, ans[u]);

        prev_pos = remove_pos(nl);
        // we will overwrite stk[prev_pos] (if prev_pos < stk_max)
        if (prev_pos < stk_max) prev_line = stk[prev_pos];

        stk_max = prev_pos;
        stk[stk_max++] = nl;
    }

    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d + w);
    }

    // rollback
    stk_max = prev_max;
    if (prev_pos != -1 && prev_pos < prev_max) stk[prev_pos] = prev_line;
}

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

    int n;
    cin >> n;

    // safety: ensure MAXN is enough
    if (n + 5 > MAXN) {
        // In contests you'd just set MAXN big enough; this is just a guard.
        // If this triggers, increase MAXN above.
        return 0;
    }

    adj.assign(n, {});
    REP(i, n - 1) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        --u; --v;
        adj[u].pushb({v, w});
        adj[v].pushb({u, w});
    }

    har.assign(n, {0, 0});
    ans.assign(n, 0);

    REP(i, 1, n) cin >> har[i].fir >> har[i].sec;

    stk_max = 0;
    dfs(0);

    REP(i, 1, n) cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

• Subtask 1: 50 / 100