Submission #1282287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282287		quan606303	Harbingers (CEOI09_harbingers)	C++20	100 / 100	73 ms	19852 KiB

harbingers

///0-0 : what is your motivation, quan606303?
///quan606303 : Hutao
/*idea :



*/
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=100000+7;
vector<pair<int,int> > adj[maxn];
struct point
{
    int a, b;
};
int eva(point a,int x)
{
    return a.a*x+a.b;
}
bool bad(point l1,point l2,point l3)
{
    return (((double)(l2.b-l1.b)/(l1.a-l2.a))>=((double)(l3.b-l1.b)/(l1.a-l3.a)));
}
point line[maxn];
int top=0;
int n,s[maxn],v[maxn];
struct operation
{
    int pos,top;
    point overwrite;
};
stack<operation> st;
void add_line(point x)
{
    int l=2,r=top,k=top+1;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (bad(line[mid-1],line[mid],x))
        {
            k=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    st.push({k,top,line[k]});
    top=k;
    line[k]=x;
}
void udon()
{
    operation ope=st.top();
    st.pop();
    top=ope.top;
    line[ope.pos]=ope.overwrite;
}
int get_min(int x)
{
    int l=1,r=top-1,ans=eva(line[top],x);
    while (l<=r)
    {
        int mid=(l+r)/2;
        int cnt1=eva(line[mid],x);
        int cnt2=eva(line[mid+1],x);
        if (cnt1<cnt2)
        {
            ans=min(ans,cnt1);
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}
int d[maxn],dp[maxn];
void dfs(int u,int p)
{
    if (u>1)dp[u]=get_min(v[u])+d[u]*v[u]+s[u];
    add_line({-d[u],dp[u]});
    for (auto v:adj[u])
    {
        if (v.fi==p)continue;
        d[v.fi]=d[u]+v.se;
        dfs(v.fi,u);
    }
    udon();
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //file("plinhhhh");
    cin>>n;
    for (int i=1;i<n;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    for (int i=2;i<=n;i++)cin>>s[i]>>v[i];
    dfs(1,0);
    for (int i=2;i<=n;i++)cout<<dp[i]<<" ";
    return 0;
}
/*
3
3
2 1 3
5
1 2 2 1 4
6
1 2 3 6 5 4

*/

• Subtask 1: 100 / 100