Submission #1265831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265831		nanaseyuzuki	Harbingers (CEOI09_harbingers)	C++20	60 / 100	116 ms	46708 KiB

harbingers

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

const ll INFLL = LLONG_MAX;

struct Line { ll m, b; // y = m*x + b
};

struct Change { int idx; Line prev; };

struct LiChao {
    int n;
    vector<ll> xs;
    vector<Line> seg;
    vector<Change> changes;

    LiChao(const vector<ll>& _xs) {
        xs = _xs;
        n = xs.size();
        seg.assign(4*n, {0, (ll)9e18});
    }

    inline ll eval(const Line &ln, ll x) {
        return ln.m * x + ln.b;
    }

    void add_line(Line ln, int id=1, int l=0, int r=-1) {
        if (r==-1) r = n-1;
        int m = (l+r)>>1;
        ll xl = xs[l], xm = xs[m], xr = xs[r];
        Line cur = seg[id];
        // record change
        changes.push_back({id, cur});
        // at mid, which line is better?
        if (eval(ln, xm) < eval(cur, xm)) swap(ln, seg[id]);
        // now seg[id] is better at xm
        if (l==r) return;
        if (eval(ln, xl) < eval(seg[id], xl)) {
            // new line better on left
            add_line(ln, id<<1, l, m);
        } else if (eval(ln, xr) < eval(seg[id], xr)) {
            // new line better on right
            add_line(ln, id<<1|1, m+1, r);
        }
    }

    ll query(ll xq, int id=1, int l=0, int r=-1) {
        if (r==-1) r = n-1;
        int m = (l+r)>>1;
        ll res = eval(seg[id], xq);
        if (l==r) return res;
        if (xq <= xs[m]) return min(res, query(xq, id<<1, l, m));
        else           return min(res, query(xq, id<<1|1, m+1, r));
    }

    int snapshot() { return changes.size(); }
    void rollback(int snap) {
        while ((int)changes.size() > snap) {
            auto ch = changes.back(); changes.pop_back();
            seg[ch.idx] = ch.prev;
        }
    }
};

const int MN = 100000 + 5;
int n;
vector<pair<int,ll>> adj[MN];
ll s[MN], v[MN];
ll dp[MN], distd[MN];

vector<ll> allX;

void dfs(int u, int p, LiChao &cht) {
    int snap = cht.snapshot();
    // add line for u
    cht.add_line({-distd[u], dp[u]});
    for (auto &ed : adj[u]) {
        int w = ed.first;
        ll c = ed.second;
        if (w == p) continue;
        distd[w] = distd[u] + c;
        // query cht at x = v[w]
        ll best = cht.query(v[w]);
        dp[w] = best + v[w] * distd[w] + s[w];
        dfs(w, u, cht);
    }
    cht.rollback(snap);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, w; ll c;
        cin >> u >> w >> c;
        adj[u].push_back({w, c});
        adj[w].push_back({u, c});
    }
    for (int i = 2; i <= n; i++) {
        cin >> s[i] >> v[i];
        allX.push_back(v[i]);
    }
    // include root's v if needed
    allX.push_back(0);
    sort(allX.begin(), allX.end());
    allX.erase(unique(allX.begin(), allX.end()), allX.end());

    LiChao cht(allX);
    // initialize root dp and dist
    dp[1] = 0;
    distd[1] = 0;
    // add base line y = 0*x + 0
    cht.add_line({0, 0});

    dfs(1, 0, cht);

    for (int i = 2; i <= n; i++) cout << dp[i] << " ";
    cout << '\n';
    return 0;
}

• Subtask 1: 60 / 100