제출 #875569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875569		hhnguyen	Harbingers (CEOI09_harbingers)	C++14	80 / 100	70 ms	24304 KiB

harbingers

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const int N = 1e5+5;
typedef pair <ll,ll> ii;
vector <ii> g[N];
ll i,j,n,m,k,t,dp[N],s[N],v[N],d[N],top;
struct operation
{
    ll pos,top;
    ii overwrite;
    operation(ll _p,ll _t,ii _o)
    {
        pos=_p;
        top=_t;
        overwrite=_o;
    }
};
vector <operation> undolist;
ii line[N];
ll dt(ll x,ii d)
{
    return (d.x*x+d.y);
}
bool bad(ii a,ii b,ii c)
{
    return ((b.y-a.y)*(c.x-a.x)<=(c.y-a.y)*(b.x-a.x));
}
ll getmin(ll x)
{
    ll l=0,r=top-1,ans=dt(x,line[l]);
    while(l<r)
    {
        ll mid=(l+r)/2;
        ll val1=dt(x,line[mid]);
        ll val2=dt(x,line[mid+1]);
        if(val1>val2){l=mid+1;}
        else {r=mid-1;}
        ans=min(ans,min(val1,val2));
    }
    return ans;
}
bool insertline(ii newline)
{
    ll l=1,r=top-1,k=top;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        if(bad(line[mid-1],line[mid],newline))
        {
            k=mid;
            r=mid-1;
        }
        else {l=mid+1;}
    }
    undolist.push_back(operation(k,top,line[k]));
    top=k+1;
    line[k]=newline;
    return 1;
}
void undo()
{
    operation ope=undolist.back();
    undolist.pop_back();
    top=ope.top;
    line[ope.pos]=ope.overwrite;
}
void dfs(ll u,ll par)
{
    if(u>1)
    {
        dp[u]=getmin(v[u])+s[u]+v[u]*d[u];
    }
    insertline({-d[u],dp[u]});
    for(auto x: g[u])
    {
        ll V=x.x;
        ll W=x.y;
        if(V==par){continue;}
        d[V]=d[u]+W;
        dfs(V,u);
    }
    undo();
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(ll i=1;i<n;i++)
    {
        ll U,V,W;
        cin>>U>>V>>W;
        g[U].push_back({V,W});
        g[V].push_back({U,W});
    }
    for(ll i=2;i<=n;i++)
    {
        cin>>s[i]>>v[i];
    }
    dfs(1,0);
    for(ll i=2;i<=n;i++)
    {
        cout<<dp[i]<<" ";
    }
    return 0;
}
/*
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
*/

• Subtask 1: 80 / 100