Submission #1339597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339597		halzoom	Harbingers (CEOI09_harbingers)	C++20	20 / 100	181 ms	131072 KiB

harbingers

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

#define int long long

const int N = 1e5 + 5;
const long long INF = 4e18;
const int maxN = 1e9;

int s[N], v[N], dp[N];
vector<vector<pair<int, int>>> adj;

struct Line {
    int m, c;
    Line() : m(0), c(INF) {}
    Line(int _m, int _c) : m(_m), c(_c) {}
};

int f(const Line &l, int x) {
    return l.m * x + l.c;
}

// Persistent Li Chao Tree
struct Node {
    Line line;
    Node *left = nullptr, *right = nullptr;

    Node() {}

    Node(Line v) : line(v) {}

    Node* copy() {
        Node* res = new Node();
        res->line = line;
        res->left = left;
        res->right = right;
        return res;
    }

    Node* add(Line nw, int l, int r) {
        Node* cur = copy();
        int mid = (l + r) >> 1;

        bool left_better = f(nw, l) < f(cur->line, l);
        bool mid_better  = f(nw, mid) < f(cur->line, mid);

        if (mid_better) swap(cur->line, nw);

        if (l == r) return cur;

        if (left_better != mid_better) {
            if (!cur->left) cur->left = new Node();
            cur->left = cur->left->add(nw, l, mid);
        } else {
            if (!cur->right) cur->right = new Node();
            cur->right = cur->right->add(nw, mid + 1, r);
        }

        return cur;
    }

    int query(int x, int l, int r) {
        int res = f(line, x);
        if (l == r) return res;

        int mid = (l + r) >> 1;

        if (x <= mid && left)
            return min(res, left->query(x, l, mid));
        if (x > mid && right)
            return min(res, right->query(x, mid + 1, r));

        return res;
    }
};

void go(int u, int p, int d, Node* cht) {
    if (p) {
        dp[u] = d * v[u] + s[u] + cht->query(v[u], 0, maxN);
    }

    // insert current node
    Node* nxt = cht->add(Line(-d, dp[u]), 0, maxN);

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

void solve() {
    int n;
    cin >> n;

    adj.assign(n + 1, {});

    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    for (int i = 2; i <= n; i++) {
        cin >> s[i] >> v[i];
    }

    Node* root = new Node(); // empty tree

    go(1, 0, 0, root);

    for (int i = 2; i <= n; i++) {
        cout << dp[i] << ' ';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef HALZOOM
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif

    solve();
}

• Subtask 1: 20 / 100