Submission #1245838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245838		MinhKien	Harbingers (CEOI09_harbingers)	C++20	70 / 100	119 ms	63720 KiB

harbingers

#include <unordered_map>
#include <iostream>
#include <vector>

using namespace std;

#define ll long long
#define li pair <ll, int>
#define fi first
#define se second
#define lxl pair <line*, line>

const int N = 1e5 + 10;
const ll INF = 9e18;

int n, x, y, mxv;
int a[N], v[N], w;
vector <li> g[N];

struct line {
    ll x, y;

    line () {
        x = -INF;
        y = INF;
    }

    line (ll X, ll Y) {
        x = X;
        y = Y;
    }

    ll slope() {return x;}
    ll get(ll z) {
        if (x == -INF) return INF;
        return x * z + y;
    }
};

struct lichao {
    struct node {
        node *l, *r;
        line f;

        node () {
            l = r = nullptr;
            f = line();
        }
    };

    vector <int> sz;
    vector <lxl> his;
    node *root;

    lichao() {
        sz.clear();
        his.clear();
        root = new node();
    }

    void update(int l, int r, line f, node *cur) {
        int m = (l + r) >> 1;
        if (cur->f.get(m) > f.get(m)) {
            his.push_back(lxl(&cur->f, cur->f));
            swap(cur->f, f);
        }
        if (l == r) return;

        if (f.slope() > cur->f.slope()) {
            if (cur->l == nullptr) cur->l = new node();
            update(l, m, f, cur->l);
        }
        if (f.slope() < cur->f.slope()) {
            if (cur->r == nullptr) cur->r = new node();
            update(m + 1, r, f, cur->r);
        }
    }

    void call_update(int l, int r, line f) {
        sz.push_back(his.size());
        update(l, r, f, root);
    }

    ll get(int l, int r, int u, node *cur) {
        if (cur == nullptr) return INF;
        int m = (l + r) >> 1;
        ll VAL = cur->f.get(u);
        if (l == r) return VAL;
        if (u <= m) return min(VAL, get(l, m, u, cur->l));
        return min(VAL, get(m + 1, r, u, cur->r));
    }

    void roll() {
        while (his.size() > sz.back()) {
            lxl cur = his.back();
            *cur.fi = cur.se;
            his.pop_back();
        }
        sz.pop_back();
    }
} CHT;

ll dp[N];
void DFS(int s = 1, int p = -1, ll h = 0) {
    CHT.call_update(1, mxv, line(-h, dp[s]));

    for (li z: g[s]) {
        if (z.se == p) continue;
        dp[z.se] = a[z.se] + v[z.se] * (h + z.fi) + CHT.get(1, mxv, v[z.se], CHT.root);
        DFS(z.se, s, h + z.fi);
    }

    CHT.roll();
}

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i < n; ++i) {
        cin >> x >> y >> w;
        g[x].push_back(li(w, y));
        g[y].push_back(li(w, x));
    }

    for (int i = 2; i <= n; ++i) {
        cin >> a[i] >> v[i];
        mxv = max(mxv, v[i]);
    }

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

    return 0;
}

• Subtask 1: 70 / 100