Submission #1245835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245835		MinhKien	Harbingers (CEOI09_harbingers)	C++20	40 / 100	261 ms	81900 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 {
    vector <int> sz;
    vector <lxl> his;
    unordered_map < int, line > mp;

    lichao() {
        sz.clear();
        his.clear();
        mp.clear();
    }

    void update(int l, int r, line f) {
        int m = (l + r) >> 1;
        if (mp[m].get(m) > f.get(m)) {
            his.push_back(lxl(&mp[m], mp[m]));
            swap(mp[m], f);
        }
        if (l == r) return;

        if (f.slope() > mp[m].slope()) update(l, m, f);
        if (f.slope() < mp[m].slope()) update(m + 1, r, f);
    }

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

    ll get(int l, int r, int u) {
        int m = (l + r) >> 1;
        ll cur = mp[m].get(u);
        if (l == r) return cur;
        if (u <= m) return min(cur, get(l, m, u));
        return min(cur, get(m + 1, r, u));
    }

    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]);
        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: 40 / 100