제출 #1123803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123803		Zero_OP	Harbingers (CEOI09_harbingers)	C++17	100 / 100	121 ms	17588 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 5;
const long long inf = 1e18;

struct line{
    long long a, b;
    line() : a(0), b(0) {}
    line(long long a, long long b) : a(a), b(b) {}
    long long eval(long long x){ return a * x + b; }
};

long double isect(const line& d1, const line& d2){
    return 1.0l * (d2.b - d1.b) / (d1.a - d2.a);
}

struct operation{
    int top, pos;
    line d;
    operation(int top, int pos, line d) : top(top), pos(pos), d(d) {}
};

int top;
line v[MAX];
stack<operation> ops;

int N, S[MAX], V[MAX];
long long H[MAX], ans[MAX];
vector<pair<int, int>> adj[MAX];

void initial_dfs(int u, int p){
    for(auto [v, w] : adj[u]) if(v != p){
        H[v] = H[u] + w;
        initial_dfs(v, u);
    }
}

void insert(line d){
    int l = 1, r = top - 1, change = top;
    while(l <= r){
        int mid = l + r >> 1;
        if(isect(v[mid - 1], v[mid]) >= isect(v[mid - 1], d)){
            change = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    ops.push(operation(top, change, v[change]));
    top = change + 1;
    v[change] = d;
}

void undo(){
    assert(!ops.empty());
    operation lst = ops.top(); ops.pop();

    v[lst.pos] = lst.d;
    top = lst.top;
}

long long query(long long x){
//    long long ans = inf;
//    cout << "query part : ";
//    cout << " : " << "{\n";
//    for(int i = 1; i <= top; ++i){
//        cout << v[i].a << ' ' << v[i].b << '\n';
//    }
//    cout << "}\n";
//    for(int i = 1; i <= top; ++i) ans = min(ans, v[i].eval(x));
//    return ans;

    int l = 0, r = top - 1;
    while(l < r){
        int mid = l + r >> 1;
        if(v[mid].eval(x) >= v[mid + 1].eval(x)) l = mid + 1;
        else r = mid;
    }

    return v[l].eval(x);
}

void solve(int u, int p){
    if(u > 1){
        ans[u] = S[u] + H[u] * V[u] + query(V[u]);
    }

    insert(line(-H[u], ans[u]));
//    cout << u << " : " << "{\n";
//    for(int i = 1; i <= top; ++i){
//        cout << v[i].a << ' ' << v[i].b << '\n';
//    }
//    cout << "}\n";
    for(auto [v, w] : adj[u]) if(v != p){
        solve(v, u);
    }
    undo();
}

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif //LOCAL

    cin >> N;
    for(int i = 1; i < N; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

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

    initial_dfs(1, -1);
    solve(1, -1);

    for(int i = 2; i <= N; ++i) cout << ans[i] << ' ';

    return 0;
}

• Subtask 1: 100 / 100