Submission #1158286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158286		nikolashami	Harbingers (CEOI09_harbingers)	C++20	100 / 100	112 ms	24132 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int N=1e5+4;
vector<array<int,2>>g[N];
int S[N],V[N],up[N][17],n;
ll F[N];

struct Line{
    int k=0;ll nn=0;
    ll f(int x){return(1ll*k*x)+nn;}
}C[N];

double presek(Line x,Line y){
    return(double)(y.nn-x.nn)/(x.k-y.k);
}

ll get(int x,int u){
    for(int i=16;i>=0;--i)
        if(up[u][i]>1&&presek(C[up[u][i]],C[up[up[u][i]][0]])>=(double)x)u=up[u][i];
    return(min({0ll,C[u].f(x),C[up[u][0]].f(x),C[1].f(x)}));
}

void upd(int u,Line L){
    int ou=u;u=up[u][0];
    for(int i=16;i>=0;--i)
        if(up[u][i]>1&&presek(C[up[u][i]],C[up[up[u][i]][0]])>=presek(C[up[up[u][i]][0]],L))u=up[u][i];
    if(up[u][0]&&presek(C[up[u][0]],C[u])>=presek(C[up[u][0]],L))u=up[u][0];
    up[ou][0]=u;
    for(int i=1;i<17;++i)up[ou][i]=up[up[ou][i-1]][i-1];
}

void dfs(int u,int p,int dep,ll mn){
    F[u]=S[u]+1ll*dep*V[u]+mn;
    C[u]={-dep,F[u]};
    up[u][0]=p;
    upd(u,C[u]);
    for(auto[v,w]:g[u]){
        if(!(v^p))continue;
        dfs(v,u,dep+w,get(V[v],u));
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=1,u,v,w;i<n;++i){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }

    for(int i=1;i<n;++i)
        cin>>S[i+1]>>V[i+1];

    dfs(1,0,0,0);
    for(int I=1;I<n;++I)cout<<F[I+1]<<' ';
}

• Subtask 1: 100 / 100