Submission #1271061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271061		rayan_bd	Harbingers (CEOI09_harbingers)	C++20	50 / 100	123 ms	28772 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 5;
#define int long long
const int inf = 5e18;

int ans[mxN], s[mxN], k[mxN], sz[mxN], head[mxN], sum[mxN], parent[mxN];
vector<pair<int, int>> adj[mxN];

struct Line{
    int m, c;
    Line(int _m, int _c){
        m = _m, c = _c;
    }
    int get(int x){
        return x * m + c;
    }
};
struct CHT{
    vector<Line> hull;
    bool bad(Line p, Line c, Line n){
        return (p.c - c.c) * 1.0L * (n.m - p.m) > (p.c - n.c) * 1.0L * (c.m - p.m);
    };
    void add(Line new_line){
        while(hull.size() && hull.back().m == new_line.m && hull.back().c > new_line.c) hull.pop_back();
        while(hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), new_line)) hull.pop_back();
        hull.push_back(new_line);
    }
    int query(int x){
        int st = -1, en = hull.size() - 1;
        while((en - st) > 1){
            int mid = st + (en - st) / 2;
            if(hull[mid].get(x) >= hull[mid + 1].get(x)) st = mid;
            else en = mid;
        }
        if(en < 0 || en >= hull.size()) return inf;
        return hull[en].get(x);
    }
} cht[mxN];

void dfs(int u = 1, int par = 0){
    sz[u] = 1;
    parent[u] = par;
    for(auto it : adj[u]){
        if(it.first ^ par){
            sum[it.first] = sum[u] + it.second;
            dfs(it.first, u);
            sz[u] += sz[it.first];
        }
    }
}

void hld(int u = 1, int par = 0, int chain = 1){
    head[u] = chain;
    int v = u;
    while(v){
        ans[u] = min(ans[u], cht[head[v]].query(k[u]) + s[u] + k[u] * sum[u]);
        v = parent[head[v]];
    }
    cht[head[u]].add(Line(-sum[u], ans[u]));
    int heavy = -1;
    for(auto it : adj[u]){
        if(it.first ^ par){
            if(heavy == -1) heavy = it.first;
            else{
                if(sz[it.first] > sz[heavy]){
                    heavy = it.first;
                }
            }
        }
    }
    if(heavy != -1) hld(heavy, u, chain);
    for(auto it : adj[u]){
        if(it.first ^ par && heavy != it.first){
            hld(it.first, u, it.first);
        }
    }
}

signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, u, v, d;
    cin >> n;

    for(int i = 1; i <= n - 1; ++i){
        cin >> u >> v >> d;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }

    for(int i = 2; i <= n; ++i){
        cin >> s[i] >> k[i];
    }

    for(int i = 1; i <= n; ++i) cht[i].add(Line(0, 0)), ans[i] = inf;

    dfs();
    hld();

    for(int i = 2; i <= n; ++i) cout << ans[i] << "\n";

    return 0;
}

• Subtask 1: 50 / 100