제출 #1143883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143883		yousefOsama06	Harbingers (CEOI09_harbingers)	C++20	20 / 100	150 ms	131072 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ones(n) __builtin_popcount(n)
#define msb(n) (31 - __builtin_clz(n))
#define lsb(n) __builtin_ctz(n)

const int N = 1e5 + 5, M = 1e3 + 5, LOG = 31;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

const ll maxN = 1e9 + 5;

struct Line {
    ll m, c;

    Line() : m(0), c(llinf) {}

    Line(ll m, ll c) : m(m), c(c) {}
};

ll sub(ll x, Line l) {
    return x * l.m + l.c;
}

// Persistent Li Chao
struct Node {
// range I am responsible for
    Line line;
    Node *left, *right;

    Node() {
        left = right = NULL;
    }

    Node(ll m, ll c) {
        line = Line(m, c);
        left = right = NULL;
    }

    void extend(int l, int r) {
        if (left == NULL && l != r) {
            left = new Node();
            right = new Node();
        }
    }

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

    Node *add(Line toAdd, int l, int r) {
        int mid = (l + r) / 2;
        Node *cur = copy(this);
        if (l == r) {
            if (sub(l, toAdd) < sub(l, cur->line))
                swap(toAdd, cur->line);
            return cur;
        }
        bool lef = sub(l, toAdd) < sub(l, cur->line);
        bool midE = sub(mid + 1, toAdd) < sub(mid + 1, cur->line);
        if (midE)
            swap(cur->line, toAdd);
        cur->extend(l, r);
        if (lef != midE) {
            cur->left = cur->left->add(toAdd, l, mid);
        } else {
            if (mid + 1 > r)
                return cur;
            cur->right = cur->right->add(toAdd, mid + 1, r);
        }
        return cur;
    }

    Node *add(Line toAdd) {
        return add(toAdd, 0, maxN - 1);
    }

    ll query(ll x, int l, int r) {
        int mid = (l + r) / 2;
        if (l == r || left == NULL)
            return sub(x, line);
        extend(l, r);
        if (x <= mid)
            return min(sub(x, line), left->query(x, l, mid));
        else
            return min(sub(x, line), right->query(x, mid + 1, r));
    }

    ll query(ll x) {
        return query(x, 0, maxN - 1);
    }

    void clear() {
        if (left != NULL) {
            left->clear();
            right->clear();
        }
        delete this;
    }
};

Node *tree[N];

int a[N], b[N];
ll dist[N], dp[N];
vector<pair<int, int>> adj[N];

void dfs(int u, int p = 0) {
    for (auto [v, w]: adj[u]) {
        if (v == p)
            continue;
        dist[v] = dist[u] + w;
        dp[v] = tree[u]->query(b[v]) + dist[v] * b[v] + a[v];
        tree[v] = tree[u]->add(Line(-dist[v], dp[v]));
        dfs(v, u);
    }
}

void testCase() {
    int n;
    cin >> n;
    tree[1] = new Node(0, 0);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[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] << ' ';
}


void preCompute() {

}

int32_t main() {

    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(int32_t(-log10(eps)));
    preCompute();

    int tc = 1;
//    cin >> tc;
    for (int TC = 1; TC <= tc; TC++) {
//        cout << "Case #" << TC << ": ";
        testCase();
    }
}

/*




*/

• Subtask 1: 20 / 100