Submission #1094889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094889		doducanh	Harbingers (CEOI09_harbingers)	C++14	100 / 100	74 ms	24480 KiB

harbingers

///breaker
///every second counts
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<ll,ll>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=1e5+7;
int n;
vector<ii>adj[maxn];
ll f[maxn];
ii chiso[maxn];
int maxst=0;
struct line
{
    ll m,b;
    line(ll m=0,ll b=0):m(m),b(b){}
    ll operator()(ll x){return 1ll*m*x+b;}
    friend double slope(const line &a,const line &b)
    {
        return (double)-(a.b-b.b)/(a.m-b.m);
    }
}st[maxn];
ll getmin(ll x)
{
    int l=0,r=maxst-1;
    while(l<r){
        int m=(l+r)/2;
        if(slope(st[m],st[m+1])<x){
            l=m+1;
        }
        else r=m;
    }
    return st[l](x);
}
int removeline(line x)
{
    if(maxst<2||slope(st[maxst-2],st[maxst-1])<=slope(st[maxst-1],x))return maxst;
    int l=1,r=maxst-1;
    while(l<r){
        int m=(l+r)/2;
        if(slope(st[m-1],st[m])>slope(st[m],x)){
            r=m;
        }
        else l=m+1;
    }
    return l;
}
void dfs(int u,int par,ll h)
{
    int premax,prepos;
    line preline;
    if(u!=1){
        f[u]=getmin(chiso[u].se)+chiso[u].fi+1ll*chiso[u].se*h;
        line l={-h,f[u]};
        premax=maxst;
        prepos=maxst=removeline(l);
        preline=st[maxst];
        st[maxst++]=l;
    }
    else{
        f[u]=0;
        st[maxst++]={0,0};
    }
    for(ii x:adj[u]){
        int v=x.fi;
        int w=x.se;
        if(v==par)continue;
        dfs(v,u,h+w);
    }
    if(u!=1){
        maxst=premax;
        st[prepos]=preline;
    }

}
void sol(void){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    for(int i=2;i<=n;i++){
        cin>>chiso[i].fi>>chiso[i].se;
    }
    dfs(1,0,0);
    for(int i=2;i<=n;i++)cout<<f[i]<<" ";
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

• Subtask 1: 100 / 100