Submission #987579

#	Time	Username	Problem	Language	Result	Execution time	Memory
987579		ASN49K	Paths (RMI21_paths)	C++14	0 / 100	362 ms	17240 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define pb      push_back

struct poz_max
{
    int maxx,poz;
};
poz_max merge(const poz_max& a,const poz_max& b)
{
    if(a.maxx>b.maxx || (a.maxx==b.maxx && a.poz>b.poz))
    {
        return a;
    }
    return b;
}
struct Aint
{
    int n;
    vector<poz_max>aint;
    void update(int poz,int val)
    {
        poz+=n;
        aint[poz].maxx=val;
        for(poz>>=1;poz>0;poz>>=1)
        {
            aint[poz]=merge(aint[poz<<1] , aint[poz<<1|1]);
        }
    }
    poz_max query(int l,int r)
    {
        l+=n;
        r+=n;
        poz_max rez={0,-1};
        while(l<=r)
        {
            if(l&1)rez=merge(rez , aint[l++]);
            if(!(r&1))rez=merge(rez,aint[r--]);
            l>>=1;
            r>>=1;
        }
        return rez;
    }
    void init(int n)
    {
        this->n=n;
        aint=vector<poz_max>(2*n);
        for(int i=0;i<n;i++)
        {
            aint[i+n]={0,i};
        }
    }
    Aint(){}
    Aint(int n)
    {
        init(n);
    }

};
struct Edge
{
    int to,dist;
};
const int N=100'000;
vector<Edge>g[N];
int tin[N],tout[N],rez[N];
Aint aint;
multiset<int>mp;
void change(int poz,int val1,int val2)
{
    //assert(mp.count(-val1));
    mp.erase(mp.find(-val1));
    mp.insert(-val2);
    aint.update(poz,val2);
}
void dfs(int nod,int tt)
{
    static int timp=-1;
    tin[nod]=++timp;
    for(auto &c:g[nod])
    {
        if(c.to!=tt)
        {
            dfs(c.to,nod);
            auto it=aint.query(tin[c.to] , tout[c.to]);
            change(it.poz , it.maxx , it.maxx+c.dist);
        }
    }
    tout[nod]=timp;
}
int n,k;
void reroot(int nod,int tt)
{
    for(auto &c:g[nod])
    {
        if(c.to!=tt)
        {
            auto sus=merge(aint.query(0,tin[c.to]-1) , aint.query(tout[c.to]+1 , n-1));
            auto jos=aint.query(tin[c.to] , tout[c.to]);

            change(sus.poz , sus.maxx, sus.maxx+c.dist);
            change(jos.poz , jos.maxx, jos.maxx-c.dist);

            reroot(c.to,nod);

            change(sus.poz , sus.maxx+c.dist , sus.maxx);
            change(jos.poz , jos.maxx-c.dist , jos.maxx);
        }
    }
        int old_k=k;
    for(auto &c:mp)
    {
        rez[nod]-=c;
        if(--old_k == 0)
        {
            break;
        }
    }
}
int main()
{
    cin>>n>>k;
    aint.init(n);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        x--;
        y--;
        g[x].pb({y,z});
        g[y].pb({x,z});
    }
    for(int i=0;i<n;i++)
    {
        mp.insert(0);
    }
    dfs(0,0);
    reroot(0,0);
    for(int i=0;i<n;i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

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