oj.uz

Submission #968471

# Submission time Handle Problem Language Result Execution time Memory
968471 2024-04-23T12:51:41 Z Double_Slash Harbingers (CEOI09_harbingers) C++17
100 / 100
 167 ms 26236 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;

struct Line {
	ll a, b;

    ll operator()(ll x) const {
        return a * x + b;
    }
};

struct Node {
    int l, r;
    Line *line = nullptr;
    Node *lc = nullptr, *rc = nullptr;

    ~Node() {
        delete line, delete lc, delete rc;
    }

    void add(Line *line2) {
        if (not line) {
            line = line2;
            return;
        }
        int m = (l + r) >> 1;
        bool left = (*line2)(l) < (*line)(l);
        bool mid = (*line2)(m) < (*line)(m);
        if (mid) swap(line, line2);
        if (l == r) return;
        if (left != mid) (lc ? lc : (lc = new Node{l, m}))->add(line2);
        else (rc ? rc : (rc = new Node{m + 1, r}))->add(line2);
    }

    ll query(int x) {
        if (not line) return LLINF;
        if (l == r) return (*line)(x);
        int m = (l + r) >> 1;
        Node *child = x <= m ? lc : rc;
        return min((*line)(x), child ? child->query(x) : LLINF);
    }
} *root;

int n, s[100001], v[100001], heavy[100001], sz[100001];
ll ps[100001], dp[100001];
vector<pair<int, int>> adj[100001];

int hld(int i, int par = 0) {
    for (auto [j, d]: adj[i]) {
        if (j == par) continue;
        ps[j] = ps[i] + d;
        sz[i] += hld(j, i);
        if (sz[j] > sz[heavy[i]]) heavy[i] = j;
    }
    return ++sz[i];
}

void push(int i, int par = 0) {
    dp[i] = min(dp[i], v[i] * ps[i] + root->query(v[i]));
    for (auto [j, d]: adj[i]) {
        if (j == par) continue;
        push(j, i);
    }
}

void dfs(int i, int par = 0) {
    dp[i] = min(dp[i], v[i] * ps[i] + root->query(v[i]));
    root->add(new Line{-ps[i], dp[i] += s[i]});
    for (auto [j, d]: adj[i]) {
        if (j == heavy[i] or j == par) continue;
        push(j, i);
    }
    if (heavy[i]) {
        dfs(heavy[i], i);
    }
    delete root;
    root = new Node{1, INF};
    for (auto [j, d]: adj[i]) {
        if (j == heavy[i] or j == par) continue;
        dfs(j, i);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, d;
        cin >> u >> v >> d;
        adj[u].emplace_back(v, d);
        adj[v].emplace_back(u, d);
    }
    for (int i = 2; i <= n; ++i) {
        cin >> s[i] >> v[i];
    }
    hld(1);
    memset(dp, 0x3f, sizeof dp);
    dp[1] = 0;
    root = new Node{1, INF};
    dfs(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 4 ms 5212 KB Output is correct
3 Correct 66 ms 14788 KB Output is correct
4 Correct 99 ms 19280 KB Output is correct
5 Correct 131 ms 22308 KB Output is correct
6 Correct 155 ms 26236 KB Output is correct
7 Correct 113 ms 14932 KB Output is correct
8 Correct 148 ms 20484 KB Output is correct
9 Correct 167 ms 23884 KB Output is correct
10 Correct 143 ms 21984 KB Output is correct