Submission #1204140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204140		12345678	Paths (RMI21_paths)	C++20	100 / 100	357 ms	47408 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

mt19937 rng(12345678);

ll n, k, u, v, w, mx[nx], mxr[nx], ans[nx];
vector<pair<ll, ll>> d[nx];

struct treap
{
    struct node
    {
        ll sm, sz, vl, p;
        node *l, *r;
        node(ll vl): sm(vl), sz(1), vl(vl), p(rng()), l(0), r(0) {} 
    };
    typedef node* pnode;
    pnode rt=0;
    ll size(pnode x) {return x?x->sz:0;}
    ll sum(pnode x) {return x?x->sm:0;}
    void update(pnode x)
    {
        if (!x) return;
        x->sz=size(x->l)+size(x->r)+1;
        x->sm=sum(x->l)+sum(x->r)+x->vl;
    }
    void merge(pnode l, pnode r, pnode &k)
    {
        if (!l) k=r;
        else if (!r) k=l;
        else if (l->p>=r->p) merge(l->r, r, l->r), k=l;
        else merge(l, r->l, r->l), k=r;
        update(k);
    }
    void splitlowerbound(pnode &l, pnode &r, pnode k, ll value)
    {
        if (!k) return l=r=0, void();
        if (k->vl<value) splitlowerbound(k->r, r, k->r, value), l=k;
        else splitlowerbound(l, k->l, k->l, value), r=k;
        update(l);
        update(r);
    }
    void splitleft(pnode &l, pnode &r, pnode k, ll key)
    {
        if (!k) return l=r=0, void();
        if (1+size(k->l)<=key) splitleft(k->r, r, k->r, key-(1+size(k->l))), l=k;
        else splitleft(l, k->l, k->l, key), r=k;
        update(l);
        update(r);
    }
    void splitright(pnode &l, pnode &r, pnode k, ll key)
    {
        if (!k) return l=r=0, void();
        if (1+size(k->r)<=key) splitright(l, k->l, k->l, key-(1+size(k->r))), r=k;
        else splitright(k->r, r, k->r, key), l=k;
        update(l);
        update(r);
    }
    void add(ll x)
    {
        //cout<<"x "<<x<<'\n';
        pnode p1, p2;
        splitlowerbound(p1, p2, rt, x);
        //cout<<"add "<<p1<<' '<<p2<<' '<<rt<<'\n';
        merge(p1, new node(x), p1);
        //cout<<"p1 "<<p1->vl<<'\n';
        merge(p1, p2, rt);
        //cout<<"after "<<rt<<' '<<rt->vl<<'\n';
    }
    void remove(ll x)
    {
        pnode p1, p2, p3;
        splitlowerbound(p1, p2, rt, x);
        splitleft(p2, p3, p2, 1);
        merge(p1, p3, rt);
    }
    ll query()
    {
        pnode p1, p2;
        splitright(p1, p2, rt, k);
        ll tmp=p2->sm;
        merge(p1, p2, rt);
        return tmp;
    }
    void show(pnode x)
    {
        if (!x) return;
        show(x->l);
        cout<<x->vl<<' ';
        show(x->r);
    }
} t;

void dfs(int u, int p)
{
    for (auto [v, w]:d[u])
    {
        if (v==p) continue;
        dfs(v, u);
        mx[u]=max(mx[u], mx[v]+w);
        if (mx[v]) t.remove(mx[v]);
        t.add(mx[v]+w);
    }
    //t.show(t.rt);
    //cout<<'\n';
    //cout<<"after "<<u<<' '<<t.size(t.rt)<<'\n';
}

void dfs2(int u, int p)
{
    ans[u]=t.query();
    //cout<<"debug "<<u<<' '<<mxr[u]<<'\n';
    //if (u==1||u==2) t.show(t.rt), cout<<'\n';
    pair<ll, ll> cmx, smx;
    for (auto [v, w]:d[u])
    {
        if (v==p) continue;
        if (mx[v]+w>cmx.first) smx=cmx, cmx={mx[v]+w, v};
        else if (mx[v]+w>smx.first) smx={mx[v]+w, v};
    }
    //cout<<"cmx "<<cmx.first<<' '<<cmx.second<<'\n';
    //cout<<"smx "<<smx.first<<' '<<smx.second<<'\n';
    for (auto [v, w]:d[u])
    {
        if (v==p) continue;
        t.remove(mx[v]+w);
        t.add(mx[v]);
        ll cur=mxr[u];
        if (v==cmx.second) cur=max(cur, smx.first);
        else cur=max(cur, cmx.first);
        t.remove(cur);
        t.add(cur+w);
        mxr[v]=cur+w;
        dfs2(v, u);
        t.remove(cur+w);
        t.add(cur);
        t.add(mx[v]+w);
        t.remove(mx[v]);
    }
}

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

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32