Submission #1108194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108194		Pekiban	Harbingers (CEOI09_harbingers)	C++17	100 / 100	137 ms	31048 KiB

harbingers

// perzistentni stak
// dfs od cvora 1
// radis CHT na perzistentnom staku 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back

struct line {
    ll k, c;
    ll operator()(ll x) {
        return k * x + c;
    }
};
const int N = 1e5 + 5, LOG = 17;
vector<array<int, 2>> g[N];
int up[LOG][N], a[N], b[N], C = 0, d = 0;
ll dp[N];
line st[N];
ld intersect(line &A, line &B) {
    return (ld)(A.c - B.c) / (B.k - A.k);
}
ll f(ll x) {
    int u = d;
    for (int i = LOG-1; i >= 0; --i) {
        if (up[i][u] > 1 && intersect(st[up[i][u]], st[up[0][up[i][u]]]) >= x) {
            u = up[i][u];
        }
    }
    if (up[0][u] && intersect(st[u], st[up[0][u]]) >= x) u = up[0][u];
    return min(st[u](x), st[1](x));
}
void dfs(int s, int e = -1, ll D = 0) {
    if (s > 1)  dp[s] = a[s] + b[s] * D + f(b[s]);
    for (auto [u, w] : g[s]) {
        if (u == e) continue;
        st[++C] = {-D, dp[s]};
        int d1 = d;
        for (int i = LOG-1; i >= 0; --i) {
            if (up[i][d] > 1 && intersect(st[up[i][d]], st[up[0][up[i][d]]]) >= intersect(st[C], st[up[0][up[i][d]]])) {
                d = up[i][d];
            }
        }
        if (up[0][d] && intersect(st[C], st[up[0][d]]) <= intersect(st[d], st[up[0][d]])) d = up[0][d];
        up[0][C] = d;
        for (int i = 1; i < LOG; ++i)   up[i][C] = up[i-1][up[i-1][C]];
        d = C;
        dfs(u, s, D + w);
        d = d1;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    for (int i = 2; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }
    dfs(1);
    for (int i = 2; i <= n; ++i) {
        cout << dp[i] << ' ';
    }
    cout << '\n';
}

• Subtask 1: 100 / 100