Submission #1235394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235394		felipe_massa	Harbingers (CEOI09_harbingers)	C++20	100 / 100	67 ms	31912 KiB

harbingers

#include<bits/stdc++.h>
#define int long long

using namespace std;
#define size(u) (int)(u).size()
#define pb push_back
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define EPS 1e-9

constexpr int N = 1e5+5;
int dp[N], S[N], V[N], d[N];
vector<pair<int, int>> adj[N];

struct Line {
    int a, b;
    int eval(int x) { return a * x + b; }
    double operator^(Line oth) {
        return (double)(oth.b - b) / (a - oth.a);
    }
};

struct Cht {
    vector<Line> hull = vector<Line>(N);
    vector<pair<int &, int>> op;
    int ptr = -1;
    int query(int x) {
        int l = 0, r = ptr-1, ans = ptr;
        while (l <= r) {
            int mid = (l+r)/2;
            if ((hull[mid] ^ hull[mid+1]) < x) {
                l = mid + 1;
            } else {
                ans = mid; r = mid-1; 
            }
        }
        return hull[ans].eval(x);
    }
    void update(Line cur) {
        int l = 0, r = ptr-1, ans = ptr;
        while (l <= r) {
            int mid = (l+r)/2;
            if ((hull[mid] ^ hull[mid+1]) > (hull[mid] ^ cur)) {
                ans = mid; r = mid-1;
            } else {
                l = mid + 1;
            }
        }
        op.pb({hull[ans+1].a, hull[ans+1].a});
        op.pb({hull[ans+1].b, hull[ans+1].b});
        op.pb({ptr, ptr});
        hull[ans+1] = cur;
        ptr = ans+1; 
    }
    int snapshot() { return size(op); };
    void rb(int until) {
        while (size(op) > until) {
            op.back().first = op.back().second;
            op.pop_back();
        }
    }
};
Cht cht;
// dp[i] = S[i] + (d[i]-d[j]) * V[i] + dp[j];
// dp[i] = S[i] + V[i] * d[i] - V[i] * d[j] + dp[j];
// dp[i] = S[i] + V[i] * d[i] - (V[i] * d[j] - dp[j]);

void dfs(int cur = 0, int par = 0, int dpt = 0) {
    int snap = cht.snapshot();
    d[cur] = dpt;
    if (cur) {
        dp[cur] = S[cur] + V[cur] * d[cur] - cht.query(V[cur]);
    }
    cht.update({d[cur], -dp[cur]});
    for (auto p : adj[cur]) {
        int u = p.first, w = p.second;
        if (u != par) {
            dfs(u, cur, dpt + w);
        }
    }
    cht.rb(snap);
}

signed main() {
    fastio;
    int n; cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b, c; cin >> a >> b >> c;
        --a, --b;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
    for (int i = 1; i < n; i++) {
        cin >> S[i] >> V[i];
    }
    dfs();
    for (int i = 1; i < n; i++) {
        cout << dp[i] << " \n"[i==n-1];
    }
}

• Subtask 1: 100 / 100