Submission #536562

#	Time	Username	Problem	Language	Result	Execution time	Memory
536562		Sorting	Harbingers (CEOI09_harbingers)	C++17	100 / 100	123 ms	24580 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 1e5 + 3;

ll curr_sz;
pair<ll, ll> lines[N];

vector<pair<ll, ll>> adj[N];
int n;

ll s[N], v[N], dp[N];

ll ip(pair<ll, ll> l1, pair<ll, ll> l2){
    return (l1.second - l2.second) / (l2.first - l1.first); 
}

ll eval(pair<ll, ll> l, ll x){
    return l.first * x + l.second;
}

void dfs(int u, int p = -1, ll dist = 0){
    if(u == 1) dp[u] = 0;
    else{
        ll x = v[u];
        dp[u] = dist * v[u] + s[u];

        ll l = 0, r = curr_sz - 1;
        while(l != r){
            ll mid = (l + r) >> 1;
            if(eval(lines[mid], x) >= eval(lines[mid + 1], x))
                l = mid + 1;
            else
                r = mid;
        }
        dp[u] += eval(lines[l], x);
    }

    pair<ll, ll> line = {-dist, dp[u]};
    ll prev_sz = curr_sz;
    pair<ll, pair<ll, ll>> go_back{-1, pair{-1, -1}};

    if(curr_sz <= 1)
        lines[curr_sz++] = line;
    else{
        int l = 1, r = curr_sz;
        while(l != r){
            int mid = (l + r) >> 1;
            if(ip(lines[mid - 1], lines[mid]) >= ip(lines[mid], line))
                r = mid;
            else
                l = mid + 1;
        }
        go_back = {l, lines[l]};
        lines[l] = line;
        curr_sz = l + 1;
    } 

    for(auto [to, d]: adj[u]){
        if(to == p) continue;
        dfs(to, u, dist + d);
    }

    curr_sz = prev_sz;
    if(go_back.first != -1)
        lines[go_back.first] = go_back.second;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n - 1; ++i){
        int u, v, d;
        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] >> v[i];

    dfs(1);

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

• Subtask 1: 100 / 100