Submission #1209219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209219		russvn123	Harbingers (CEOI09_harbingers)	C++20	70 / 100	1094 ms	24392 KiB

harbingers

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define endl '\n'
#define pb push_back
using namespace std;
const int max_n=1e5+1;
int n,d,x,y,h[max_n];
ll dp[max_n];
ll S[max_n],V[max_n];
pair<int,ll> node;
vector<pair<int,int>> v[max_n];
vector<pair<int,ll>> cht;
void INP()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>n;
    for (int i=1;i<n;++i)
    {
        cin>>x>>y>>d;
        v[x].pb({y,d});
        v[y].pb({x,d});
    }
    for (int i=1;i<n;++i)
        cin>>S[i+1]>>V[i+1];
}
ll eval(pair<int,ll> a,ll x)
{
    return a.fi*x+a.se;
}
bool calc(pair<int,ll> &a,pair<int,ll> &b,pair<int,ll> &c)
{
    // (b.se-a.se)/(a.fi-b.fi)<=(c.se-a.se)/(a.fi-c.fi)
    return (double)(b.se-a.se)/(a.fi-b.fi)<=(double)(c.se-a.se)/(a.fi-c.fi);
    //return (b.se-a.se)*(a.fi-c.fi)<=(c.se-a.se)*(a.fi-b.fi);
}
int l,r,mid,res;
void dfs(int u,int p)
{
    dp[u]=h[u]*V[u]+S[u];
    int sz=cht.size();
    if (sz!=0)
    {
        if (sz==1)
        dp[u]+=eval(cht[0],V[u]); else
        {
            l=0; r=sz-2; res=0;
            while (l<=r)
            {
                mid =(l+r)>>1;
                if (eval(cht[mid],V[u])>=eval(cht[mid+1],V[u]))
                {
                    res=mid;
                    l=mid+1;
                } else
                r=mid-1;
            }
            if (res+1<=sz-1&&eval(cht[res],V[u])>=eval(cht[res+1],V[u]))
            ++res;
            //for (auto it : cht)
            //cout<<u<<' '<<eval(it,V[u])<<endl;
            dp[u]+=eval(cht[res],V[u]);
        }
    }
    // dp[u] = dist[u]*v[u] + s[u] -dist[v]*v[u] + dp[v]
    node = {-h[u],dp[u]};
    vector<pair<int,ll>> roll;
    while (cht.size()>=2&&calc(node,cht.back(),cht[cht.size()-2]))
    {
        roll.pb(cht.back());
        cht.pop_back();
    }
    cht.push_back(node);
    for (auto &it : v[u])
    if (it.fi!=p)
    {
        h[it.fi]=h[u]+it.se;
        dfs(it.fi,u);
    }
    cht.pop_back();
    if (roll.size()>0)
    for (int i=roll.size()-1;i>=0;--i)
    cht.pb(roll[i]);
}
int main()
{
    INP();
    h[1]=0;
    dfs(1,0);
    for (int i=2;i<=n;++i)
        cout<<dp[i]<<' ';
    return 0;
}

• Subtask 1: 70 / 100