Submission #1122808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122808		12345678	Harbingers (CEOI09_harbingers)	C++20	0 / 100	114 ms	26996 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

#define ll long long

mt19937 rng(time(0));

const ll nx=1e5+5, inf=1e18;

ll n, h[nx], u, v, w, dp[nx], s[nx], vl[nx];
vector<pair<ll, ll>> d[nx];

ll divfloor(ll a, ll b)
{
    if ((a%b)==0||((a^b)>=0)) return a/b;
    return a/b-1;
}

ll isect(ll m1, ll c1, ll m2, ll c2)
{
    return divfloor(c2-c1, m1-m2);
}

struct treap
{
    struct node
    {
        ll m, c, p, key, sz;
        node *l, *r;
        node(ll m, ll c, ll p): l(0), r(0), m(m), c(c), p(p), sz(1), key(rng()){}
    };
    typedef node* pnode;
    pnode rt, hd[nx], tmp;
    int size(pnode x)
    {
        return x?x->sz:0;
    }
    void update(pnode x)
    {
        if (x) x->sz=1+size(x->l)+size(x->r);
    }
    void merge(pnode l, pnode r, pnode &k)
    {
        if (!l) return k=r, void();
        if (!r) return k=l, void();
        //cout<<"merging\n";
        //cout<<"l "<<l->m<<' '<<l->c<<' '<<l->key<<' '<<l->sz<<' '<<l->l<<' '<<l->r<<'\n';
        //cout<<"r "<<r->m<<' '<<r->c<<' '<<r->key<<' '<<r->sz<<' '<<r->l<<' '<<r->r<<'\n';
        if (l->key>=r->key) merge(l->r, r, l->r), k=l;
        else merge(l, r->l, r->l), k=r;
        update(k);
        //cout<<"k "<<k->m<<' '<<k->c<<' '<<k->key<<' '<<k->sz<<' '<<k->l<<' '<<k->r<<'\n';
    }
    void splithidden(pnode &l, pnode &r, pnode k, ll m, ll c)
    {
        if (!k) return l=r=0, void();
        if (isect(m, c, k->m, k->c)>=k->p) splithidden(k->r, r, k->r, m, c), l=k;
        else splithidden(l, k->l, k->l, m, c), r=k;
        update(l); update(r);
    }
    void split(pnode &l, pnode &r, pnode k, int key)
    {
        if (!k) return l=r=0, void();
        if (1+size(k->l)<=key) split(k->r, r, k->r, key-(1+size(k->l))), l=k;
        else split(l, k->l, k->l, key), r=k;
        update(l); update(r);
    }
    ll query(pnode k, ll x)
    {
        if (x>k->p) return query(k->r, x);
        if (k->l&&x<=k->l->p) return query(k->l, x);
        return k->m*x+k->c;
    }
    void show(pnode k)
    {
        if (!k) return;
        show(k->l);
        cout<<"line "<<k->m<<' '<<k->c<<' '<<k->p<<' '<<k->sz<<'\n';
        show(k->r);
    }
} t;

void dfs(int u, int p)
{
    //if (t.rt) cout<<"sz "<<t.rt->sz<<'\n';
    //cout<<"show treap "<<u<<'\n';
    //t.show(t.rt);
    if (u!=1) dp[u]=t.query(t.rt, -vl[u])+h[u]*vl[u]+s[u];
    t.splithidden(t.hd[u], t.rt, t.rt, h[u], dp[u]);
    //cout<<"show hidden "<<u<<'\n';
    //t.show(t.hd[u]);
    if (u==1) t.merge(new treap::node(h[u], dp[u], inf), t.rt, t.rt);
    else 
    {
        //cout<<"new node "<<h[u]<<' '<<dp[u]<<' '<<isect(h[u], dp[u], h[p], dp[p])<<'\n';
        t.merge(new treap::node(h[u], dp[u], isect(h[u], dp[u], h[p], dp[p])), t.rt, t.rt);
        //cout<<"after merge "<<u<<'\n';
        //t.show(t.rt);
    }
    //cout<<"dp "<<u<<' '<<dp[u]<<'\n';
    for (auto [v, w]:d[u]) if (v!=p) h[v]=h[u]+w, dfs(v, u);
    t.split(t.tmp, t.rt, t.rt, 1);
    //cout<<"after split "<<u<<'\n';
    //t.show(t.rt);
    t.merge(t.hd[u], t.rt, t.rt);
    //cout<<"after end "<<u<<'\n';
    //t.show(t.rt);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    for (int i=2; i<=n; i++) cin>>s[i]>>vl[i];
    dfs(1, 1);
    for (int i=2; i<=n; i++) cout<<dp[i]<<' ';
}

• Subtask 1: 0 / 100