Submission #968497

#	Time	Username	Problem	Language	Result	Execution time	Memory
968497		rxlfd314	Harbingers (CEOI09_harbingers)	C++17	100 / 100	153 ms	23864 KiB

harbingers

#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 / 100