제출 #1152640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152640		Vovamatrix	Harbingers (CEOI09_harbingers)	C++20	20 / 100	132 ms	67252 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 int
#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
struct Line
{
    long long k,n;
    Line(){}
    Line(long long kk,long long nn) {k=kk; n=nn;}
    long long val(ll x) {return k*x+n;}
};
struct Node
{
    ll l,r;
    Line p;
    Node() {p=Line(0,LLONG_MAX/2); l=0; r=0;}
    Node(Line q) : p(q),l(0),r(0) {}
};
vector<Node> st;
ll nxt,idx;
ll x[MAXN];
ll Update(ll pv,ll tl,ll tr,Line q)
{
    ll mid=(tl+tr)/2,v=++nxt; st.pb(Node());
    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(m) swap(st[v].p,q);
    if(tl==tr) return v;
    if(l!=m)
    {
        if(!st[pv].l) {st[v].l=++nxt; st.pb(Node()); st[nxt]=Node(q);}
        else st[v].l=Update(st[pv].l,tl,mid,q);
        st[v].r=st[pv].r;
    }
    else
    {
        if(!st[pv].r) {st[v].r=++nxt; st.pb(Node()); st[nxt]=Node(q);}
        else st[v].r=Update(st[pv].r,mid+1,tr,q);
        st[v].l=st[pv].l;
    }
    return v;
}
long long Query(ll v,ll tl,ll tr,ll xx)
{
    ll mid=(tl+tr)/2; long long y=st[v].p.val(xx);
    if(tl<tr)
    {
        if(xx<=x[mid] && st[v].l) y=min(y,Query(st[v].l,tl,mid,xx));
        if(xx>x[mid] && st[v].r) y=min(y,Query(st[v].r,mid+1,tr,xx));
    }
    return y;
}
struct PLC
{
    ll L,R;
    vector<ll> roots;
    PLC() {roots={1}; nxt=1; st.pb(Node()); L=0; R=0;}
    PLC(ll lv,ll ds) {nxt=1; roots.pb(1);  st.pb(Node()); L=lv; R=ds;}
    void add(Line q)
    {
        ll rt=Update(roots.back(),L,R,q);
        roots.pb(rt);
    }
    long long query(ll i,ll x) {return Query(roots[i],L,R,x);}
}plc;
long long h[MAXN];
vector<pll> adj[MAXN];
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);
    }
}
long long dp[MAXN];
ll S[MAXN],V[MAXN];
void DFS(ll u,ll p)
{
    for(auto vw:adj[u])
    {
        ll v=vw.fi;
        if(v==p) continue;
        dp[v]=plc.query(plc.roots.size()-1,V[v])+h[v]*V[v]+S[v];
        plc.add(Line(-h[v],dp[v]));
        DFS(v,u);
        plc.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];
    idx=0;
    set<long long> vv;
    for(int i=2;i<=n;i++) vv.insert(V[i]);
    for(auto xx:vv) x[++idx]=xx;
    DFS1(1,0);
    nxt=0;
    plc=PLC(1,idx);
    plc.add(Line(0,0));
    DFS(1,0);
    for(int i=2;i<=n;i++) cout<<dp[i]<<" ";
    cout<<endl;
    return 0;
}

• Subtask 1: 20 / 100