Submission #965225

#	Time	Username	Problem	Language	Result	Execution time	Memory
965225		hhnguyen	Harbingers (CEOI09_harbingers)	C++14	90 / 100	95 ms	19904 KiB

harbingers

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

using namespace std;
typedef pair <ll,ll> ii;
const int N = 1e5+5;
vector <ii> g[N];
ll i,j,n,m,k,t,s[N],v[N],h[N],dp[N];
ll top=0;
ii d[N]; // line y = ax+b
struct pt
{
    ll pos,top;
    ii line;
};
vector <pt> list_undo;
bool bad(ii A,ii B,ii C)
{
    ii ab = {B.x - A.x,B.y - A.y};
    ii ac = {C.x - A.x,C.y - A.y};
    return (ab.x*ac.y-ab.y*ac.x >= 0);
}
ll val(ll x,ll id)
{
    return (d[id].x * x + d[id].y);
}
void add(ll x,ll y)
{
    ll l = 1,r = top - 1,pos = top;
    ii new_d = {x,y};
    while(l<=r)
    {
        ll mid = (l+r)/2;
        if(bad(d[mid-1],d[mid],new_d))
        {
            r = mid - 1;
            pos = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    list_undo.push_back({pos,top,d[pos]});
    top = pos + 1;
    d[pos] = new_d;
}
void undo()
{
    pt pre_pt = list_undo.back();
    list_undo.pop_back();
    top = pre_pt.top;
    d[pre_pt.pos] = pre_pt.line;
}
ll query(ll x)
{
    ll l = 0,r = top - 1,ans = val(x,l);
    while(l<=r)
    {
        ll mid1 = l + (r-l)/3;
        ll mid2 = r - (r-l)/3;
        if(val(x,mid1) <= val(x,mid2)){ans = val(x,mid1);r = mid2 - 1;}
        else {ans = val(x,mid2);l = mid1 + 1;}
    }
    return ans;
}
void dfs(ll u,ll par)
{
    if(u!=par)
    {
        dp[u]=query(v[u])+s[u]+v[u]*h[u];
    }
    add(-h[u],dp[u]);
    for(auto x: g[u])
    {
        ll v = x.first;
        ll w = x.second;
        if(v==par){continue;}
        h[v] = h[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,1);
    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: 90 / 100