Submission #882885

#	Time	Username	Problem	Language	Result	Execution time	Memory
882885		anarch_y	Harbingers (CEOI09_harbingers)	C++17	20 / 100	106 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
#define int long long
 
const int inf = 1e18;
 
struct line{
    int m, c;
    double p;
    int eval(int x){
        return m*x+c;
    }
};

struct CHT{
    vector<line> hull; int id;
    CHT() { id = 0;}
    double getx(int m1, int c1, int m2, int c2){
        if(m1==m2) return inf;
        else return (double)(c1-c2)/(double)(m2-m1);
    }
    void addline(int m, int c){
        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});
    }
    int best(int 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);
    }
    int fast(int x){
        while(id+1<(int)hull.size() and hull[id+1].p <= x) id++;
        return hull[id].eval(x);
    }
};

vector<pii> adj[100001];
int 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] + F[u]*dist[u];
        temp.addline(-dist[u], dp[u]);
        cht[u] = temp;
        dfs(u, s);
    }
}
 
signed 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] = 0; dp[1] = 0;
    cht[1].addline(0, 0);
    dfs(1, 0);
    for(int i=2; i<=N; i++) cout << dp[i] << ' '; 
    
}

• Subtask 1: 20 / 100