Submission #1339590

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

harbingers

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5 + 5, inf = 1e18;
int s[N], v[N], dp[N];
vector<vector<pair<int, int>>> adj;

// To get an instance : node *root = EMPTY;
typedef pair<int, int> line;
int start_x = 0, end_x = 1e18;

int sub(const line &l, int x) {
    return l.first * x + l.second;
}

double inter(const line &l1, const line &l2) {
    return (double) (l2.second - l1.second) / (l1.first - l2.first);
}

extern struct node *const EMPTY;
struct change {
    node **ptr;
    node *old;
    line l;
};
vector<change> history;

struct node {
    line l;
    node *lf, *rt;

    node() : l({0, 0}), lf(this), rt(this) {}

    node(line l) : l(l), lf(EMPTY), rt(EMPTY) {}
};

node *const EMPTY = new node;

void insert(line l, node *&cur, int ns = start_x, int ne = end_x) {
    history.push_back({&cur, cur, (cur ? cur->l : line{0, -inf})});
    if (cur == EMPTY) {
        cur = new node(l);
        return;
    }

    if (l.first == cur->l.first) {
        cur->l = max(cur->l, l);
        return;
    }

    double x = inter(l, cur->l);

    if (x < ns || x > ne) {
        if (sub(l, ns) > sub(cur->l, ns))
            cur->l = l;
        return;
    }

    int mid = ns + (ne - ns) / 2;

    if (x <= mid) {
        if (sub(l, ne) > sub(cur->l, ne))
            swap(l, cur->l);
        insert(l, cur->lf, ns, mid);
    } else {
        if (sub(l, ns) > sub(cur->l, ns))
            swap(l, cur->l);
        insert(l, cur->rt, mid + 1, ne);
    }
}

int query(int x, node *cur, int ns = start_x, int ne = end_x) {
    if (x < ns || x > ne)
        return LLONG_MIN;

    int ret = sub(cur->l, x);

    if (ns == ne)
        return ret;

    int mid = ns + (ne - ns) / 2;

    if (x <= mid)
        return max(ret, query(x, cur->lf, ns, mid));
    else
        return max(ret, query(x, cur->rt, mid + 1, ne));
}

node *T = EMPTY;

void go(int u, int p, int d) {
    if (p)
        dp[u] = d * v[u] + s[u] - query(v[u], T);
    int sz = history.size();
    insert({d, -dp[u]}, T);
    for (auto [x, add]: adj[u]) {
        if (x == p)continue;
        go(x, u, d + add);
    }

    while (history.size() > sz) {
        auto [ptr, old, l] = history.back();
        *ptr = old;
        if (old != EMPTY)
            old->l = l;
        history.pop_back();
    }
}

void solve() {
    int n;
    cin >> n;
    adj.assign(n + 1, {});
    for (int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for (int i = 2; i <= n; ++i)
        cin >> s[i] >> v[i];

    go(1, 0, 0);
    for (int i = 2; i <= n; ++i)
        cout << dp[i] << ' ';
}

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

    int test = 1;
//    cin >> test;

    for (int i = 1; i <= test; ++i) {
        solve();
    }
    return 0;
}

• Subtask 1: 30 / 100