Submission #1270966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270966		rayan_bd	Harbingers (CEOI09_harbingers)	C++20	50 / 100	75 ms	17220 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 100;
#define int long long
const int inf = 2e18;
int ans[mxN], s[mxN], k[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){
        if(hull.size() == 0){
            cout << "fuck off\n";
            return 0;
        }
        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;
void dfs(int u = 1, int par = 0, int d = 0){
    if(u > 1){
        int y = cht.query(k[u]);
        cht.add(Line(-d, y + s[u] + k[u] * d));
        ans[u] = y + s[u] + k[u] * d;
    }    for(auto it : adj[u]){
        if(it.first ^ par){
            dfs(it.first, u, d + it.second);
        }
    }
}
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];
    }

    cht.add(Line(0, 0));

    dfs();

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

    return 0;
}

• Subtask 1: 50 / 100