oj.uz

Submission #970469

# Submission time Handle Problem Language Result Execution time Memory
970469 2024-04-26T15:01:54 Z vjudge1 Harbingers (CEOI09_harbingers) C++17
100 / 100
 91 ms 21636 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = int(1e5) + 5;

using ll = int64_t;

const ll INF = LLONG_MAX / 2;

struct line {
    ll a, b;

    ll eval(ll x) {
        return ll(1) * a * x + b;
    }

    ll div(ll a, ll b) const {
        return a / b - ((a ^ b) < 0 && a % b);
    }

    ll intersect(const line &oth) const {
        if (a == oth.a) {
            return b <= oth.b ? -INF : INF;
        }
        return div(b - oth.b, oth.a - a);
    }
};

int n, m;
int S[N], V[N];
ll dp[N], h[N];
line cht[N];
vector<pair<int, int>> g[N];
stack<pair<int, line>> his;

ll qry(ll x) {
    int l = 1, r = m - 1, ans = 1;
    while (l <= r) {
        int md = (l + r) / 2;
        if (cht[md].intersect(cht[md + 1]) < x) {
            l = md + 1;
            ans = md + 1;
        } else {
            r = md - 1;
        }
    }
    return cht[ans].eval(x);
}

void add(ll a, ll b) {
    int l = 1, r = m - 1, ans = m + 1;
    line x = {a, b};
    while (l <= r) {
        int md = (l + r) / 2;
        if (cht[md].intersect(cht[md + 1]) >= cht[md + 1].intersect(x)) {
            ans = md + 1;
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    his.emplace(m, cht[ans]);
    cht[ans] = x;
    m = ans;
}

void dfs(int u, int p) {
    if (u > 1) {
        dp[u] = -qry(V[u]) + S[u] + h[u] * V[u];
        add(h[u], -dp[u]);
    }
    for (auto [v, w] : g[u]) {
        if (v ^ p) {
            h[v] = h[u] + w;
            dfs(v, u);
        }
    }
    if (u > 1) {
        cht[m] = his.top().second;
        m = his.top().first;
        his.pop();
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    for (int i = 2; i <= n; ++i) {
        cin >> S[i] >> V[i];
    }
    m = 1;
    cht[1] = {0, 0};
    dfs(1, 1);
    for (int i = 2; i <= n; ++i) {
        cout << dp[i] << " ";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 36 ms 11936 KB Output is correct
4 Correct 50 ms 15184 KB Output is correct
5 Correct 46 ms 18516 KB Output is correct
6 Correct 60 ms 21636 KB Output is correct
7 Correct 38 ms 12828 KB Output is correct
8 Correct 78 ms 17104 KB Output is correct
9 Correct 91 ms 19024 KB Output is correct
10 Correct 78 ms 17864 KB Output is correct