Submission #1153596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153596		Vovamatrix	Harbingers (CEOI09_harbingers)	C++20	0 / 100	107 ms	37004 KiB

harbingers

//https://oj.uz/problem/view/CEOI09_harbingers
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb long double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"

#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define MAXN 100007
#define K 17
vector<pll> adj[MAXN];
struct Line
{
    ll k,n;
    Line(){}
    Line(ll kk,ll nn) {k=kk; n=nn;}
    ll val(ll x) {return k*x+n;}
};
ldb Intersect(Line a,Line b) {return (ldb)(a.n-b.n)/(b.k-a.k);}
ll S[MAXN],V[MAXN],up[MAXN][K],dp[MAXN],nxt,uu;
Line st[MAXN];
ll Query(ll u,ll x)
{
    for(int j=K-1;j>=0;j--)
    {
        if(up[u][j]>1 && Intersect(st[up[u][j]],st[up[up[u][j]][0]])>=x) u=up[u][j];
    }
    if(up[u][0] && Intersect(st[u],st[up[u][0]])>=x) u=up[u][0];
    return st[u].val(x);
}
void DFS(ll u,ll p,ll h)
{
    if(u>1) dp[u]=Query(p,V[u])+V[u]*h+S[u];
    for(auto vw:adj[u])
    {
        ll v=vw.fi,w=vw.sc;
        if(v==p) continue;
        st[++nxt]=Line(-h,dp[u]);
        ll vv=uu; uu=nxt;
        for(int j=K-1;j>=0;j--)
        {
            if(up[vv][j]>1 && Intersect(st[up[vv][j]],st[up[up[vv][j]][0]])>=Intersect(st[nxt],st[up[vv][j]])) vv=up[vv][j];
        }
        if(up[vv][0] && Intersect(st[vv],st[up[vv][0]])>=Intersect(st[nxt],st[up[vv][0]])) vv=up[vv][0];
        up[nxt][0]=vv;
        for(int j=1;j<K;j++) up[nxt][j]=up[up[nxt][j-1]][j-1];
        DFS(v,u,h+w);
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    ll n; cin>>n;
    for(int i=1;i<n;i++)
    {
        ll u,v,w; cin>>u>>v>>w;
        adj[u].pb({v,w}); adj[v].pb({u,w});
    }
    for(int i=2;i<=n;i++) cin>>S[i]>>V[i];
    DFS(1,0,0);
    for(int i=2;i<=n;i++) cout<<dp[i]<<" ";
    cout<<endl;
    return 0;
}

• Subtask 1: 0 / 100