Submission #1245886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245886		MinhKien	Harbingers (CEOI09_harbingers)	C++20	100 / 100	94 ms	26804 KiB

harbingers

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

using namespace std;

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

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;
    }

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

ld intersect(line x, line y) {
    return 1.0l * (x.y - y.y) / (1.0l * (y.x - x.x));
}

struct CHT {
    vector <lxl> his;
    vector <line> lines;
    int sz;

    CHT () {
        sz = 0;
        his.clear();
        lines.resize(N);
    }

    void update(line f) {
        int l = 1, r = sz - 1, need = sz;
        while (l <= r) {
            int m = (l + r) >> 1;

            if (intersect(f, lines[m - 1]) <= intersect(lines[m - 1], lines[m])) {
                need = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        his.push_back(lxl(ii(sz, need), lines[need]));
        sz = need + 1;
        lines[need] = f;
    }

    ll get(int val) {
        int l = 0, r = sz - 1;
        while (l < r) {
            int m = (l + r) >> 1;

            if (lines[m].get(val) >= lines[m + 1].get(val)) l = m + 1;
            else r = m;
        }

        return lines[l].get(val);
    }

    lxl cur;
    void roll() {
        cur = his.back(); his.pop_back();
        sz = cur.fi.fi;
        lines[cur.fi.se] = cur.se;
    }
} cht;

ll dp[N];
void DFS(int s = 1, int p = -1, ll h = 0) {
    if (s != 1) dp[s] = a[s] + v[s] * h + cht.get(v[s]);
    cht.update(line(-h, dp[s]));

    for (li z: g[s]) {
        if (z.se == p) continue;
        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: 100 / 100