제출 #478192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
478192		vitkute	Harbingers (CEOI09_harbingers)	C++11	10 / 100	184 ms	65540 KiB

harbingers

/// [_DukkSooCee3305_]
/// Date : 05/10/2021
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define ALL(i_) i_.begin(), i_.end()
#define Random(lf_, rt_) (lf_ + rand() % (rt_ - lf_ + 1))
#define PB push_back
#define sz(i_) ((int)(i_).size())
#define reset(i_, x_) memset(i_, x_, sizeof i_)
#define TASK "HARBINGERS"

typedef long long ll;
typedef long double ld;
typedef pair<int, ll> ii;

const int oo = 1000000099;
const int mod = 1000000007;
const int maxn = 100011;

int n;
vector<ii> ke[maxn];
int t[maxn], g[maxn], d[maxn];
ll dp[maxn];

struct line{
    ll a, b;
    ll f(ll x){ return (a*x + b); };
};

struct CHT{
    deque<line> dq;
    vector<line> undoList[maxn];
    ld slope(line l1, line l2){
        return (ld) (l2.b - l1.b) / (ld) (l2.a - l1.a);
    }
    bool better(line new_line, line a, line b){
        return (slope(new_line, a) <= slope(new_line, b));
    }
    void add_line(int pos, line new_line){
        while(sz(dq) >= 2 && better(new_line, dq[sz(dq) - 2], dq.back())) dq.pop_back();
        dq.push_back(new_line);
        FOR(i, 0, sz(dq) - 1){
            undoList[pos].PB(dq[i]);
        }
    }
    ll get_values(ll x){
        if(sz(dq) == 1) return dq[0].f(x);
        int lf = 0, rt = sz(dq) - 1;
        ll res = dq[lf].f(x);
        while(rt - lf >= 0){
            int mid = (rt - lf)/2 + lf;
            ll f1 = dq[mid].f(x);
            ll f2 = dq[mid + 1].f(x);
            if(f1 > f2) lf = mid + 1;
            else rt = mid - 1;
            res = min(res, min(f1, f2));
        }
        return res;
    }
    void undo(int u){
        while(!dq.empty()) dq.pop_back();
        FOR(i, 0, sz(undoList[u]) - 1) dq.push_back(undoList[u][i]);
    }

} convex_hull;

namespace process{

    void DFS(int u, int par){
        if(u > 1){
            dp[u] = t[u] + g[u] * d[u];
            dp[u] += convex_hull.get_values(g[u]);
        }
        convex_hull.add_line(u, {-d[u], dp[u]});
        for(ii x : ke[u]){
            int v = x.first;
            ll w = x.second;
            if(v == par) continue;
            d[v] = d[u] + w;
            DFS(v, u);
            convex_hull.undo(u);
        }
    }

    void solve(){
        d[1] = 0;
        dp[1] = 0;
        DFS(1, -1);
        FOR(i, 2, n) cout << dp[i] << " ";
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
    cin >> n;
    FOR(i, 1, n-1){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        ke[u].PB({v, w});
        ke[v].PB({u, w});
    }
    FOR(i, 2, n) cin >> t[i] >> g[i];
    process::solve();
    return 0;
}

• Subtask 1: 10 / 100