제출 #1193576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193576		jahongir	Harbingers (CEOI09_harbingers)	C++20	40 / 100	229 ms	111560 KiB

harbingers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,
					 tree_order_statistics_node_update>;
 
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(i,a,b) for(int i = (a); i <= (b); i++)

typedef complex<ll> point;
const ll inf = 1e18;

ll dot(point a, point b){
    return (conj(a)*b).real();
}

ll calc(point a, ll x){
    return dot(a,{x,1});
}

struct LiChao{
    struct Node{
        point f;
        Node(ll m, ll c){
            f = {m,c};
        }
        int l = -1, r = -1;
    };
    vector<Node> st;
    ll szl, szr;
    int tim = 0;

    void update(int i, int wch){
        if(st[i].l == -1 && wch==0){
            st[i].l = ++tim;
            st.pb({0,inf});
        }
        if(st[i].r == -1 && wch==1){
            st[i].r = ++tim;
            st.pb({0,inf});
        }
    }

    void init(ll l, ll r){
        szl = l, szr = r;
        st.pb({0,inf});
    }

    void add(int i, ll l, ll r, point val){
        ll m = (l+r)>>1;
        bool lef = calc(val,l) < calc(st[i].f,l);
        bool mid = calc(val,m) < calc(st[i].f,m);
        if(mid) swap(st[i].f,val);
        if(l==r) return;
        if(lef != mid){
            update(i,0);
            add(st[i].l,l,m,val);
        }
        else{
            update(i,1);
            add(st[i].r,m+1,r,val);
        }
    }

    void add(point val){
        add(0,szl,szr,val);
    }

    ll get(int i, ll l, ll r, ll x){
        ll res = calc(st[i].f,x);
        if(l==r) return res;
        int m = (l+r)>>1;
        if(x <= m){
            update(i,0);
            return min(res,get(st[i].l,l,m,x));
        }
        update(i,1);
        return min(res,get(st[i].r,m+1,r,x));
    }

    ll get(ll x){
        return get(0,szl,szr,x);
    }

    void clear(){
        st.clear();
    }
};

const int mxn = 1e5+10;
vector<pi> g[mxn];
int val[mxn][2];

int par[mxn], head[mxn];
int dep[mxn],heavy[mxn];
LiChao st[mxn];

int dfs(int u, int p, int d){
    int sz = 1, mx = 0;

    for(auto [v,c] : g[u]) if(v!=p){
        par[v] = u; dep[v] = d+c;
        int vsz = dfs(v,u,d+c);
        sz += vsz;
        if(mx < vsz)
            mx = vsz, heavy[u] = v;
    }

    return sz;
}

void dfs2(int u, int h){
    head[u] = h;
    if(heavy[u]) dfs2(heavy[u],h);
    for(auto [v,c] : g[u]) if(v!=par[u] && v!=heavy[u])
        dfs2(v,v);
}

ll dp[mxn];

void dfs(int u){
    int v = u;
    dp[u] = inf;
    while(v){
        dp[u] = min(dp[u],1ll*dep[u]*val[u][1] + val[u][0] + st[head[v]].get(val[u][1]));
        v = par[head[v]];
    }

    st[head[u]].add({-dep[u],dp[u]});

    for(auto [v,c] : g[u]) if(v!=par[u]){
        if(v!=heavy[u]) st[v].init(1,1e9);
        dfs(v);
    }

}


void solve(){
    int n; cin >> n;
    for(int i = 1; i < n; i++){
        int u,v,c; cin >> u >> v >> c;
        g[u].pb({v,c}); g[v].pb({u,c});
    }
    for(int i = 2; i <= n; i++) cin >> val[i][0] >> val[i][1];

    st[1].init(1,1e9); st[1].add({0,0});
    dfs(1,0,0); dfs2(1,1); dfs(1);

    for(int i = 2; i <= n; i++) cout << dp[i] << ' ';
}
 
 
signed main(){
    // freopen("262144.in","r",stdin);
    // freopen("262144.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while(t--) solve();
}

• Subtask 1: 40 / 100