Submission #1152167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152167		Vovamatrix	Harbingers (CEOI09_harbingers)	C++20	0 / 100	55 ms	15544 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 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 MAXM 4000007
vector<pll> adj[MAXN];
ll S[MAXN],V[MAXN],dp[MAXN],x[MAXN],nxt,idx,h[MAXN];
vector<ll> roots;
struct Line
{
    ll k,n;
    Line(){}
    Line(ll kk,ll nn) {k=kk; n=nn;}
    ll val(ll x) {return k*x+n;}
};
struct Node
{
    ll l,r;
    Line p;
    Node(){}
    Node(Line q) {l=0; r=0; p=q;}
}st[MAXM];
ll Update(ll v,ll pv,ll tl,ll tr,Line q)
{
    ll mid=(tl+tr)/2,id=++nxt;
    st[v].p=st[pv].p;
    bool l=q.val(x[tl])<st[v].p.val(x[tl]);
    bool m=q.val(x[mid])<st[v].p.val(x[mid]);
    if(mid) swap(st[v].p,q);
    if(tl==tr) return id;
    if(l!=m)
    {
        if(!st[pv].l) {st[v].l=++nxt; st[nxt]=Node(q);}
        else st[v].l=Update(st[v].l,st[pv].l,tl,mid,q);
        st[v].r=st[pv].r;
    }
    else
    {
        if(!st[pv].r) {st[v].r=++nxt; st[nxt]=Node(q);}
        else st[v].r=Update(st[v].r,st[pv].r,mid+1,tr,q);
        st[v].l=st[pv].l;
    }
    return id;
}
ll Query(ll v,ll tl,ll tr,ll xx)
{
    if(tl==tr) return st[v].p.val(xx);
    else
    {
        ll mid=(tl+tr)/2,y=st[v].p.val(xx);
        if(xx<=x[mid]) return min(y,Query(st[v].l,tl,mid,xx));
        else return min(y,Query(st[v].r,mid+1,tr,xx));
    }
}
void DFS1(ll u,ll p)
{
    for(auto vw:adj[u])
    {
        ll v=vw.fi,w=vw.sc;
        if(v==p) continue;
        h[v]=h[u]+w;
        DFS1(v,u);
    }
}
void DFS(ll u,ll p)
{
    for(auto vw:adj[u])
    {
        ll v=vw.fi;
        if(v==p) continue;
        dp[v]=Query(roots.size()-1,1,idx,V[v])+h[v]*V[v]+S[v];
        ll rt=Update(rt,roots.back(),1,idx,Line(-h[v],dp[v]));
        roots.pb(rt);
        DFS(v,u);
        roots.pop_back();
    }
}
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];
    set<ll> ss;
    for(int i=2;i<=n;i++) ss.insert(V[i]);
    idx=0;
    for(auto w:ss) x[++idx]=w;
    nxt=1; h[0]=0; roots.pb(1);
    cout<<"";
    DFS1(1,0); DFS(1,0);
    for(int i=2;i<=n;i++) cout<<dp[i]<<" ";
    return 0;
}

• Subtask 1: 0 / 100