Submission #1200219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200219		Muhammad_Aneeq	Harbingers (CEOI09_harbingers)	C++20	60 / 100	53 ms	19624 KiB

harbingers

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
int const N=1e5+10;
vector<pair<int,int>>nei[N]={};
int dist[N]={};
int dp[N]={};
int V[N],S[N];
vector<pii>hull={};
inline bool com(pii a,pii b)
{
    if (a.fi/a.se!=b.fi/b.se)
        return a.fi/a.se < b.fi/b.se;
    a.fi%=a.se;
    b.fi%=b.se;
    return (a.fi*b.se<b.fi*a.se);
}
inline bool cw(pii a,pii b,pii c)
{
    return com({b.fi-a.fi,a.se-b.se},{c.fi-b.fi,b.se-c.se});
}
inline void insert(pii x)
{
    if (hull.size()&&hull.back()==x) return;
    while (hull.size()>1&&!cw(hull[hull.size()-2],hull.back(),x))
        hull.pop_back();
    hull.push_back(x);
}
inline int vl(pii a,int x)
{
    return x*a.se+a.fi;
}
int query(int x)
{
    int ans=vl(hull[0],x);
    int st=1,en=hull.size()-1;
    while (st<=en)
    {
        int mid=(st+en)/2;
        int ans1=vl(hull[mid-1],x),ans2=vl(hull[mid],x);
        if (ans1<ans2)
        {
            ans=min(ans,ans1);
            en=mid-1;
        }
        else
        {
            ans=min(ans,ans2);
            st=mid+1;
        }
    }
    return ans;
}
vector<int>anc;
void dfs1(int u,int p=-1)
{
    if (p!=-1)
    {
        dp[u]=1e18;
        for (auto i:anc)
        {
            dp[u]=min(dp[u],dp[i]+(dist[u]-dist[i])*V[u]+S[u]);
        }
    }
    anc.push_back(u);
    for (auto [i,w]:nei[u])
    {
        if (i==p) continue;
        dist[i]=dist[u]+w;
        dfs1(i,u);
    }
    anc.pop_back();
}
void dfs(int u,int p=-1)
{
    dp[u]=query(V[u])+V[u]*dist[u]+S[u];
    insert({dp[u],-dist[u]});
    for (auto [i,w]:nei[u])
    {
        if (i==p) continue;
        dist[i]=dist[u]+w;
        dfs(i,u);
    }
}
inline void solve()
{
    int n;
    cin>>n;
    for (int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        nei[u].push_back({v,w});
        nei[v].push_back({u,w});
    }
    for (int i=2;i<=n;i++)
        cin>>S[i]>>V[i];
    if (n<=2500)
    {
        dfs1(1);
        for (int i=2;i<=n;i++)
            cout<<dp[i]<<' ';
        cout<<endl;return;
    }
    for (auto [i,w]:nei[1])
    {
        hull={};
        insert({0,0});
        dist[i]=w;
        dfs(i,1);
    }
    for (int i=2;i<=n;i++)
        cout<<dp[i]<<' ';
    cout<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

• Subtask 1: 60 / 100