Submission #1200531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200531		Cabralbonzao	Harbingers (CEOI09_harbingers)	C++20	20 / 100	232 ms	119472 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

#define N 100010
#define K 102
#define MV 1000000010
#define INFLL 1000000000000000010
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector< ll > vl;
typedef vector< pll > vll;

struct Node
{
    ll a;
    ll b;
    ll u;

    ll getval(ll x)
    {
        return a*x+b;
    }

};

struct Line
{
    vector<Node>nodes;
    ll lef=-1;
    ll rig=-1;
};

stack<ll>pilha;
vector<Line>lines;
Line lx;
vector<pll>grafo[N];
ll dp[N];
ll d[N];
ll s[N];
ll c[N];
bool active[N];

ll createl()
{
    lines.pb(lx);
    lines.back().nodes.pb({0,0,1});
    return lines.size()-1;
}

void update(ll i,ll l,ll r,Node cur)
{
    ll mid=((l+r)>>1LL);
    ll lef=lines[i].lef;
    ll rig=lines[i].rig;
    while(!active[lines[i].nodes.back().u])
    {
        lines[i].nodes.ppb();
    }
    ll pos=lines[i].nodes.size()-1;
    if(l==r-1)
    {
        if(cur.getval(l)<lines[i].nodes[pos].getval(l))
        {
            lines[i].nodes.pb(cur);
        }
        return;
    }
    Node auxc=cur;
    Node auxl=lines[i].nodes[pos];
    bool swi=false;
    if(auxc.a>auxl.a)
        swap(auxc,auxl),swi=true;
    if(auxc.getval(mid)<auxl.getval(mid))
    {
        lines[i].nodes.pb(auxc);
        cur=auxl;
        if(lef==-1)
            lef=createl();
        update(lef,l,mid,cur);
    }else
    {
        lines[i].nodes.pb(auxl);
        cur=auxc;
        if(rig==-1)
            rig=createl();
        update(rig,mid,r,cur);
    }
    lines[i].lef=lef;
    lines[i].rig=rig;
    return;
}

ll query(ll i,ll l,ll r,ll x)
{
    if(i==-1)
        return INFLL;
    while(!active[lines[i].nodes.back().u])
    {
        lines[i].nodes.ppb();
    }
    ll pos=lines[i].nodes.size()-1;
    if(l==r-1)
        return lines[i].nodes[pos].getval(x);
    ll mid=((l+r)>>1LL);
    ll lef=lines[i].lef;
    ll rig=lines[i].rig;
    if(x<mid)
        return min(lines[i].nodes[pos].getval(x),query(lef,l,mid,x));
    return min(lines[i].nodes[pos].getval(x),query(rig,mid,r,x));
}

void DFS(ll u,ll p)
{
    active[u]=true;
    if(u==p)
    {
        createl();
    }
    dp[u]=d[u]*s[u]+c[u]+query(0,0,MV,s[u]);
    Node cur={-d[u],dp[u],u};
    update(0,0,MV,cur);
    for(auto [v,w] : grafo[u])
    {
        if(v==p)
            continue;
        d[v]=d[u]+w;
        DFS(v,u);
    }
    active[u]=false;
    return;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    
    ll n,u,v,w;

    cin >> n;
    for(ll i=2;i<=n;i++)
    {
        cin >> u >> v >> w;
        grafo[u].pb({v,w});
        grafo[v].pb({u,w});
    }
    for(ll i=2;i<=n;i++)
    {
        cin >> c[i] >> s[i];
    }
    DFS(1,1);
    for(ll i=2;i<=n;i++)
    {
        cout << dp[i] << ((i==n) ? '\n' : ' ');
    }

	return 0;
}

• Subtask 1: 20 / 100