Submission #1034462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034462		ASN49K	Paths (RMI21_paths)	C++14	100 / 100	329 ms	21840 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7;
struct first_k_sum
{
    int k;
    i64 sum=0;
    multiset<i64>used,non_used;
    void insert(i64 x)
    {
        used.insert(x);
        sum+=x;
        if((int)used.size()>k)
        {
            i64 el=*used.begin();
            sum-=el;
            used.erase(used.find(el));
            non_used.insert(el);
        }
    }
    void erase(i64 x)
    {
        auto it=used.find(x);
        if(it!=used.end())
        {
            sum-=x;
            used.erase(it);
            if(non_used.size())
            {
                i64 val=*non_used.rbegin();
                non_used.erase(non_used.find(val));
                used.insert(val);
                sum+=val;
            }
        }
        else
        {
            non_used.erase(non_used.find(x));
        }
    }
};

struct poz_max
{
    i64 maxx;
    int 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,i64 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];
i64 rez[N];
Aint aint;
first_k_sum mp;
void change(int poz,i64 val1,i64 val2)
{
    mp.erase(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);
        }
    }
    rez[nod]=mp.sum;
}
main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    mp.k=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;
}

Compilation message (stderr)

Main.cpp:154:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  154 | main()
      | ^~~~

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