Submission #883161

#	Time	Username	Problem	Language	Result	Execution time	Memory
883161		anarch_y	Harbingers (CEOI09_harbingers)	C++17	20 / 100	93 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) begin(x), end(x)
#define pb push_back
 
const ll inf = 1e18;
 
struct line{
    ll m, c;
    long double p;
    ll eval(ll x){
        return (ll)(m*x+c);
    }
};
 
struct CHT{
    vector<line> hull; int id;
    CHT() {id = 0;}
    double getx(ll m1, ll c1, ll m2, ll c2){
        if(m1==m2) return inf;
        else return (long double)(c1-c2)/(long double)(m2-m1);
    }
    void addline(int m, int c){
        long double p = -inf;
        while(!hull.empty()){
            line last = hull.back();
            p = getx(m, c, last.m, last.c);
            if(p==inf){
                if(c>last.c) return;
                else hull.pop_back();
            }
            else if(p<last.p) hull.pop_back();
            else break;
        }
        hull.pb((line){m, c, p});
    }
    ll best(ll x){
        int k = 0;
        int L = 0, R = hull.size()-1;
        while(L<=R){
            int mid = (L+R)/2;
            if(hull[mid].p <= x){
                k = mid; L = mid+1;
            }
            else R = mid-1;
        }
        return hull[k].eval(x);
    }
    ll fast(ll x){
        while(id+1<(int)hull.size() and hull[id+1].p <= x) id++;
        return hull[id].eval(x);
    }
};
 
vector<pii> adj[100001];
ll dist[100001], dp[100001];
CHT cht[100001];
int S[100001], F[100001];
 
void dfs(int s, int e){
    for(auto pr: adj[s]){
        int u = pr.first;
        if(u == e) continue;
        dist[u] = dist[s] + pr.second;
        CHT temp = cht[s];
        dp[u] = temp.best(F[u]) + S[u] + (ll)(F[u]*dist[u]);
        temp.addline(-dist[u], dp[u]);
        cht[u] = temp;
        dfs(u, s);
    }
    cht[s].hull.clear();
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N; cin >> N;
    for(int i=0; i<N-1; i++){
        int a, b, d; cin >> a >> b >> d;
        adj[a].pb({b, d}); adj[b].pb({a, d});
    }
    for(int i=2; i<=N; i++){
        cin >> S[i] >> F[i];
    }
    dist[1] = 0LL; dp[1] = 0LL;
    cht[1].addline(0LL, 0LL);
    dfs(1, 0);
    for(int i=2; i<=N; i++) cout << dp[i] << ' '; 
    
}

• Subtask 1: 20 / 100