Submission #1278468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278468		Ice_man	Harbingers (CEOI09_harbingers)	C++20	50 / 100	71 ms	26700 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
const ll LINF = (ll)4e18;

struct CHT {
    // Lines in the hull are stored in order of decreasing slope for min query
    vector<pll> hull;

    // Intersection check with integer arithmetic to avoid precision issues
    bool bad(const pll &l1, const pll &l2, const pll &l3) {
        // return true if l2 is useless
        // cross(l1,l2) >= cross(l2,l3)
        return (l2.second - l1.second) * (l1.first - l3.first) >= (l3.second - l1.second) * (l1.first - l2.first);
    }

    void add_line(pll ln) {
        while(hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), ln))
            hull.pop_back();
        hull.push_back(ln);
    }

    ll query(ll x) {
        if(hull.empty()) return LINF;
        int l = 0, r = hull.size()-1;
        while(l < r) {
            int m = (l+r)/2;
            ll val1 = hull[m].first * x + hull[m].second;
            ll val2 = hull[m+1].first * x + hull[m+1].second;
            if(val1 > val2) l = m+1;
            else r = m;
        }
        return hull[l].first * x + hull[l].second;
    }
};

const int MAXN = 200005;
int n;
vector<pair<int,int>> g[MAXN];
ll waitt[MAXN], speed[MAXN], dp[MAXN], dista[MAXN];
int parent0[MAXN], sz[MAXN], heavy[MAXN], head[MAXN], depth0[MAXN];
vector<int> nodes_by_depth[MAXN];
CHT cht[MAXN]; // one CHT per chain

void dfs_sz(int u, int p){
    parent0[u] = p;
    sz[u] = 1;
    heavy[u] = -1;
    nodes_by_depth[depth0[u]].push_back(u);
    for(auto &e : g[u]){
        int v = e.first, w = e.second;
        if(v==p) continue;
        depth0[v] = depth0[u]+1;
        dista[v] = dista[u]+w;
        dfs_sz(v,u);
        sz[u] += sz[v];
        if(heavy[u]==-1 || sz[v]>sz[heavy[u]]) heavy[u]=v;
    }
}

void dfs_hld(int u, int h){
    head[u] = h;
    if(heavy[u]!=-1) dfs_hld(heavy[u],h);
    for(auto &e : g[u]){
        int v = e.first;
        if(v==parent0[u] || v==heavy[u]) continue;
        dfs_hld(v,v);
    }
}

// Query from node u to root along chains
ll query(int u){
    ll res = LINF;
    while(u){
        int h = head[u];
        res = min(res, cht[h].query(speed[u]));
        u = parent0[h];
    }
    return res;
}

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

    cin >> n;
    for(int i=1;i<=n;++i) g[i].clear();
    for(int i=1;i<=n-1;++i){
        int x,y,z; cin >> x >> y >> z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }
    for(int i=2;i<=n;++i) cin >> waitt[i] >> speed[i];

    dista[1] = 0;
    depth0[1] = 0;
    parent0[1] = 0;
    dfs_sz(1,0);
    dfs_hld(1,1);

    dp[1] = 0;
    cht[head[1]].add_line({-dista[1],dp[1]});

    // process nodes level by level
    for(int d=1;d<=n;++d){
        if(nodes_by_depth[d].empty()) continue;
        // compute dp[node]
        for(int node : nodes_by_depth[d]){
            ll best = query(node);
            ll val = waitt[node] + speed[node]*dista[node];
            if(best != LINF) val = min(val, best + speed[node]*dista[node] + waitt[node]);
            dp[node] = val;
        }
        // add lines to their chains
        for(int node : nodes_by_depth[d]){
            cht[head[node]].add_line({-dista[node], dp[node]});
        }
    }

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

• Subtask 1: 50 / 100