Submission #1263813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263813		VMaksimoski008	Harbingers (CEOI09_harbingers)	C++20	100 / 100	63 ms	18872 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5;

struct line {
    ll m, b;
    ll operator()(ll x) { return m * x + b; }
};

long double isect(const line &a, const line &b) {
    return (long double)(b.b - a.b) / (a.m - b.m);
}

struct convex_hull {
    vector<line> hull;

    bool cross(const line &a, const line &b, const line &c) {
        return isect(a, c) <= isect(a, b);
    }

    bool cross(const line &a) {
        int sz = hull.size();
        return cross(hull[sz-2], hull[sz-1], a);
    }

    void add(line f) {
        while(hull.size() >= 2 && cross(f)) hull.pop_back();
        hull.push_back(f);
    }

    ll get(ll x) {
        if(hull.empty()) return 1e18;
        int l=0, r=hull.size()-2, ans=hull.size()-1;
        while(l <= r) {
            int m = (l + r) / 2;
            if(isect(hull[m], hull[m+1]) >= x)
                ans = m, r = m - 1;
            else
                l = m + 1;
        }
        return hull[ans](x);
    }
};

ll dp[N];
vector<pii> g[N];
convex_hull cht[N];
int n, par[N], top[N], sub[N], S[N], V[N], dist[N];

int dfs_init(int u, int p) {
    par[u] = p;
    sub[u] = 1;

    for(auto [v, w] : g[u]) if(v ^ p) {
        dist[v] = dist[u] + w;
        sub[u] += dfs_init(v, u);
    }

    return sub[u];
}

void hld(int u, int p, int t=1) {
    top[u] = t;
    dp[u] = S[u] + (ll)V[u] * dist[u];
    
    int v = u;
    while(v) {
        dp[u] = min(dp[u], (ll)S[u] + (ll)V[u] * dist[u] + cht[top[v]].get(V[u]));
        v = par[ top[v] ];
    }

    int ch = 0;
    for(auto [v, _] : g[u])
        if(v != p && sub[v] > sub[ch]) ch = v;

    if(u > 1) cht[t].add({ -dist[u], dp[u] });
    
    for(auto [v, _] : g[u])
        if(v != p && v != ch) hld(v, u, v);
    if(ch) hld(ch, u, t);
}

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

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

    for(int i=2; i<=n; i++)
        cin >> S[i] >> V[i];
    dfs_init(1, 0);
    hld(1, 0);
    for(int i=2; i<=n; i++)
        cout << dp[i] << " ";
}

• Subtask 1: 100 / 100