Submission #1122908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122908		12345678	Harbingers (CEOI09_harbingers)	C++20	100 / 100	139 ms	28348 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, mx;
        node *l, *r;
        node(ll m, ll c, ll p): l(0), r(0), m(m), c(c), p(p), sz(1), mx(p), key(rng()){}
    };
    typedef node* pnode;
    pnode rt, hd[nx], tmp;
    int size(pnode x)
    {
        return x?x->sz:0;
    }
    ll getmax(pnode x)
    {
        return x?x->mx:-inf;
    }
    void update(pnode x)
    {
        if (x) x->sz=1+size(x->l)+size(x->r), x->mx=max(x->mx, getmax(x->r));
    }
    pnode getleft(pnode x)
    {
        if (x->l) return getleft(x->l);
        return x;
    }
    void merge(pnode l, pnode r, pnode &k)
    {
        if (!l) return k=r, void();
        if (!r) return k=l, void();
        if (l->key>=r->key) merge(l->r, r, l->r), k=l;
        else merge(l, r->l, r->l), k=r;
        update(k);
    }
    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->mx)) return query(k->l, x);
        return k->m*x+k->c;
    }
} t;

void dfs(int u, int p)
{
    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]);
    if (u==1) t.merge(new treap::node(h[u], dp[u], inf), t.rt, t.rt);
    else t.merge(new treap::node(h[u], dp[u], isect(h[u], dp[u], t.getleft(t.rt)->m, t.getleft(t.rt)->c)), t.rt, t.rt);
    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);
    t.merge(t.hd[u], t.rt, 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: 100 / 100