Submission #660307

#	Time	Username	Problem	Language	Result	Execution time	Memory
660307		leroycut	Harbingers (CEOI09_harbingers)	C++17	100 / 100	112 ms	21964 KiB

harbingers

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
 
const int N = 1e5 + 3;
const ll INF = 2e12 + 3;

struct LINE{
    ll k = 0, b = 0;
    LINE(ll _k = 0, ll _b = 0) : k(_k), b(_b) {}
};

ld cross(LINE a, LINE b){
    return (ld)(b.b - a.b) / (ld)(a.k - b.k);
}

ll f(LINE a, ll x){
    return a.k * x + a.b;
}

int n, st_end = 0;
ll V[N], S[N], dp[N];
vector<pair<int, ll>> g[N];
LINE st[N];

ll min_val(ll x){
    int l = 0, r = st_end - 1;
    while(r - l > 0){
        int m = (l + r) / 2;
        if(cross(st[m], st[m + 1]) <= x){
            l = m + 1;
        }else{
            r = m;
        }
    }
    return f(st[l], x);
}

int remove_el(LINE cur){
    if(st_end < 2 || cross(st[st_end - 1], cur) >= cross(st[st_end - 1], st[st_end - 2])){
        return st_end;
    }

    int l = 1, r = st_end - 1;
    while(r - l > 0){
        int m = (l + r) / 2;
        if(cross(st[m], cur) < cross(st[m], st[m - 1])){
            r = m;
        }else{
            l = m + 1;
        }
    }
    return l;
}

void dfs(int v, int p, ll d){
    int prev_pos, prev_st_end;
    LINE prev_line;
    if(p == 0){
        dp[v] = 0;
        st[st_end++] = {0, 0};
    }else{
        dp[v] = S[v] + d * V[v] + min_val(V[v]);
        LINE cur(-d, dp[v]);
        prev_st_end = st_end;
        prev_pos = st_end = remove_el(cur);
        prev_line = st[st_end];
        st[st_end++] = cur;
    }

    for(auto i : g[v]){
        if(i.first == p) continue;
        dfs(i.first, v, d + i.second);
    }

    if(p != 0){
        st[prev_pos] = prev_line;
        st_end = prev_st_end;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 0; i < n - 1; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

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

    dfs(1, 0, 0);

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

• Subtask 1: 100 / 100