제출 #1270950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270950		rayan_bd	Harbingers (CEOI09_harbingers)	C++20	0 / 100	2 ms	836 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
const int mxN = 3000;
#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){
        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 = -1, int d = 0){
    int y = 0;
    if(u != 1) cht.query(d);
    ans[u] = y + s[u] + k[u] * d;
    cht.add(Line(d, 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];
    }
    dfs();

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

    return 0;
}

• Subtask 1: 0 / 100