Submission #522554

#	Time	Username	Problem	Language	Result	Execution time	Memory
522554		fcmalkcin	Paths (RMI21_paths)	C++17	100 / 100	578 ms	39932 KiB

Main

/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>
using namespace std;

#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define For(i,a,b) for (ll i=a;i<=b;i++)

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+100;
const ll mod=998244353  ;
const ll base=2e9+10000;

/// you will be the best but now you just are trash
/// goal 3/7

ll res[maxn];
vector<pll> adj[maxn];
pll st[4*maxn];
ll pos[maxn];
ll n, k;
pll mer(pll a,pll b)
{
    if (a.ff>=b.ff)
        return a;
    return b;
}
void update(ll id,ll left,ll right,ll x,ll diff)
{
    if (x>right||x<left)
        return ;
    if (left==right)
    {
        st[id]=make_pair(diff,left);
        return ;
    }
    ll mid=(left+right)/2;
    update(id*2,left,mid,x,diff);
    update(id*2+1,mid+1,right,x,diff);
    st[id]=mer(st[id*2],st[id*2+1]);
}
pll get(ll id,ll left,ll right,ll x,ll y)
{
    if (x>right||y<left)
        return make_pair(-1,0);
    if (x<=left&&y>=right)
        return st[id];
    ll mid=(left+right)/2;
    return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
struct tk
{
    pll st[4*maxn];
    ll la[4*maxn];
    tk()
    {
        for (int i=0; i<4*maxn; i++)
        {
            st[i]=make_pair(0,0);
        }
        memset(la,0,sizeof(la));
    }
    pll mer(pll a,pll b)
    {
        if (a.ff>=b.ff)
            return a;
        return b;
    }
    void dosth(ll id,ll left,ll right)
    {
        st[id*2].ff+=la[id];
        st[id*2+1].ff+=la[id];
        la[id*2]+=la[id];
        la[id*2+1]+=la[id];
        la[id]=0;
        return ;
    }
    void update(ll id,ll left,ll right,ll x,ll y,ll diff)
    {
        if (x>right||y<left)
            return ;
        if (x<=left&&y>=right)
        {
            st[id].ff+=diff;
            la[id]+=diff;
            if (left==right)
                st[id].ss=left;
            return ;
        }
        dosth(id,left,right);
        ll mid=(left+right)/2;
        update(id*2,left,mid,x,y,diff);
        update(id*2+1,mid+1,right,x,y,diff);
        st[id]=mer(st[id*2],st[id*2+1]);
    }
    pll get(ll id,ll left,ll right,ll x,ll y)
    {
        if (x>right||y<left)
            return make_pair(-1,0);
        if (x<=left&&y>=right)
            return st[id];
        dosth(id,left,right);
        ll mid=(left+right)/2;
        return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
    }
} man;
set<pll> st1;
set<pll,greater<pll>> st2;
ll ans=0;
ll cnt=0;
ll f[maxn];
ll l[maxn];
ll dep[maxn];
vector<ll> vt;
ll val[maxn];
bool dd[maxn];
ll anc[maxn];

void add(ll u)
{
    if (st1.size()<k)
    {
        st1.insert(make_pair(val[u],u));
        ans+=val[u];
    }
    else
    {
        if ((*st1.begin())<make_pair(val[u],u))
        {
            auto p=(*st1.begin());
            st1.erase(st1.begin());
            st1.insert(make_pair(val[u],u));
            ans+=val[u];
            ans-=p.ff;
            st2.insert(p);
        }
        else
        {
            st2.insert(make_pair(val[u],u));
        }
    }
}
void ers(ll u)
{
    if (st1.count(make_pair(val[u],u)))
    {
        st1.erase(make_pair(val[u],u));
        ans-=val[u];
        if (st2.size())
        {
            auto p=(*st2.begin());
            st2.erase(p);
            st1.insert(p);
            ans+=p.ff;
        }
    }
    else
    {
        st2.erase(make_pair(val[u],u));
    }
}
void change(ll u,ll val1)
{
    if (val[u])
    {
        ers(u);
    }
    update(1,1,n,f[u],val1);
    val[u]=val1;
    add(u);
}
void dfs(ll u,ll par)
{
    anc[u]=par;
    cnt++;
    f[u]=cnt;
    pos[cnt]=u;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll w=p.ss;
        if (to==par)
            continue;
        dep[to]=dep[u]+w;
        dfs(to,u);
    }
    l[u]=cnt;
    if (l[u]==f[u])
    {
        vt.pb(u);
    }
}
ll mxl[maxn];
void dfs1(ll u,ll par)
{
    mxl[u]=u;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll w=p.ss;
        if (to==par)
            continue;
        dfs1(to,u);
        if (val[mxl[to]]>val[mxl[u]])
            mxl[u]=mxl[to];
    }
}
void dfs2(ll u,ll par,pll mxpre)
{
    res[u]=ans;
    for (auto p1:adj[u])
    {
        ll to=p1.ff;
        ll w=p1.ss;
        if (to==par)
            continue;
        ll posnxt=mxl[to];
        ll valnw=dep[posnxt]-dep[u];
        change(posnxt,valnw-w);
        auto p=mer(get(1,1,n,f[u],f[to]-1),get(1,1,n,l[to]+1,l[u]));
        if (p.ff>mxpre.ff)
        {
            p=make_pair(p.ff,pos[p.ss]);
        }
        else
        {
            p=mxpre;
        }
        change(p.ss,p.ff+w);
        dfs2(to,u,make_pair(p.ff+w,p.ss));
        change(posnxt,valnw);
        change(p.ss,p.ff);

    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin>> n>> k;
    pll root=make_pair(0,1);
    for (int i=1; i<=n-1; i++)
    {
        ll x, y, w;
        cin>>x>> y>> w;
        adj[x].pb(make_pair(y,w));
        adj[y].pb(make_pair(x,w));
        root=max(root,make_pair((ll)adj[x].size(),x));
        root=max(root,make_pair((ll)adj[y].size(),y));
    }
    if (n==1)
    {
        cout <<0;
        return 0;
    }
    dd[0]=1;
    dfs(root.ss,0);
   // cout <<root.ss<<endl;
    k=min(k,(ll)vt.size());
    for (auto to:vt)
    {
        man.update(1,1,n,f[to],l[to],dep[to]);
        // cout <<to<<" "<<dep[to]<<endl;
    }
    for (int i=1; i<=vt.size(); i++)
    {
        auto p=man.st[1];
        ll u=pos[p.ss];
        change(u,p.ff);
        ll nw=u;
        while (!dd[nw])
        {
            dd[nw]=1;
            man.update(1,1,n,f[nw],l[nw],-(dep[nw]-dep[anc[nw]]));
            nw=anc[nw];
        }
    }
    dfs1(root.ss,0);
    dfs2(root.ss,0,make_pair(-1,0));
    for (int i=1;i<=n;i++)
    {
        cout <<res[i]<<endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'void add(long long int)':
Main.cpp:129:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  129 |     if (st1.size()<k)
      |         ~~~~~~~~~~^~
Main.cpp: In function 'void dfs1(long long int, long long int)':
Main.cpp:208:12: warning: unused variable 'w' [-Wunused-variable]
  208 |         ll w=p.ss;
      |            ^
Main.cpp: In function 'int main()':
Main.cpp:279:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |     for (int i=1; i<=vt.size(); i++)
      |                   ~^~~~~~~~~~~
Main.cpp:251:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:252:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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