Submission #1038379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038379		manizare	Paths (RMI21_paths)	C++17	100 / 100	513 ms	253252 KiB

Main

#include <bits/stdc++.h>
 

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <ll,int>
#define PII pair<pii , pii>
#define ld long double 
#define ll long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 1e5 + 10  ,  N = 1e5 +1 , lg = 20 , maxq = 202 , sq = 333   , inf = 1e18 +100 , maxk = 2022 ;
int n , k , mark[maxn] , id[maxn] , par[maxn]  , st[maxn] , en[maxn] , c = 1 , pw[maxn] ;
ll dis[maxn] , ans[maxn]   ; 
vector <pii> G[maxn] ;int ti = 1 ;  
struct node{
    pii mx , mn ;
    ll lz = 0 ;
};
node operator+(node a , node b){
    node r ;
    r.mx.F = max(a.mx.F , b.mx.F) ;
    if(r.mx.F == a.mx.F)r.mx.S = a.mx.S ;
    else r.mx.S = b.mx.S ; 

    r.mn.F = min(a.mn.F , b.mn.F) ;
    if(r.mn.F == a.mn.F)r.mn.S = a.mn.S ;
    else r.mn.S = b.mn.S ; 

    r.lz = 0 ;
    return r ; 
}
struct segtree{
    vector <pair<int,node> > his ; 
    node s[4*maxn] ; ll sm =0;
    int ma[maxn*4] , vaz = 0 ;
    inline void H(int x){
        if(ma[x] != ti){
            ma[x] =ti;
            his.pb({x,s[x]}) ;
        }
    }
    void bui(int p = 1, int l = 1 ,int r =n){
        int mid = (l+r)/2 , pl=p<<1 ,pr =p<<1|1 ;
        sm =0 ;
        if(p == 1)rep(i , 1,4*n)ma[i] = 0 ;
        if(l == r){
            s[p].mx = {0,l} ;
            s[p].mn = {0,l} ; 
            return ; 
        }
        bui(pl,l,mid) ;
        bui(pr ,mid+1,r);
        s[p] = s[pl] + s[pr] ;
    }
    void shi(int p){
        int pl =p<<1 ,pr =p<<1|1 ;
        ll w = s[p].lz ;
        H(pl) ; H(pr) ; 
        s[pl].lz += w ; 
        s[pr].lz += w ;
        
        s[pr].mx.F += w ;
        s[pl].mn.F += w ;
        
        s[pl].mx.F += w ;
        s[pr].mn.F += w; 

        s[p].lz =0 ; 
    }
    void upd(int le ,int ri , ll w ,int p = 1,int l =1 ,int r =n){
        H(p) ;
        int mid = (l+r)/2 , pl=p<<1 ,pr =p<<1|1 ;
        if(l > ri || le > r)return;
        if(le <= l && r<= ri){
            s[p].mx.F += w;
            s[p].mn.F += w; 
            s[p].lz += w; 
            sm += w; 
            return ;
        }
        if(vaz==0)shi(p) ;
        upd(le,ri,w,pl,l,mid);
        upd(le,ri,w,pr,mid+1,r);
        s[p] = s[pl] + s[pr] ;
    }
    node que(int le ,int ri , int p =1 ,int l =1 ,int r =n){
        int mid = (l+r)/2 ,pl=p<<1, pr =p<<1|1 ;
        if(le <= l && r <= ri)return s[p] ;
        H(p) ;
        if(vaz==0)shi(p) ; 
        if(mid >= ri)return que(le,ri,pl,l,mid);
        if(mid < le)return que(le,ri,pr,mid+1,r);
        return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
    }
    void rem(int x , int p =1 ,int l = 1, int r =n){
        H(p) ;
        int mid = (l+r)/2 , pl=p<<1 ,pr =p<<1|1 ;
        if(l > x || x > r)return ; 
        if(l == r){
            sm -= s[p].mx.F ; 
            s[p].mx = {-inf,l} ; 
            s[p].mn = {inf,l} ; 
            return ; 
        }
        rem(x,pl,l,mid);rem(x,pr,mid+1,r);
        s[p] = s[pl]+s[pr] ;
    }
    void add(int x ,ll w , int p =1 , int l =1 ,int r = n){ 
        H(p) ; 
        int mid = (l+r)/2 , pl=p<<1 ,pr =p<<1|1 ;
        if(l > x || x > r)return ;
        if(l == r){
            sm += w; 
            s[p].mx = {w,l} ;s[p].mn = {w,l} ;
            return ; 
        }
        add(x,w,pl,l,mid);add(x,w,pr,mid+1,r) ;
        s[p] = s[pl] + s[pr] ; 
    }        
};
segtree v0 , v1 ; 

void dfs(int v ,int p =0){
    st[v] = c ; c++ ; 
    id[st[v]] = v; 
    for(auto [u,w] : G[v]){
        if(u == p)continue ; 
        par[u] = v ;
        pw[u] = w; 
        dis[u] = dis[v] + w; 
        dfs(u ,v) ; 
    }
    en[v] = c-1 ; 
}
void ch(vector <pii> vec , int w){
    node r1, r2  ; 
    rep(i , 0, sz(vec)-1){
        int l =vec[i].F , r = vec[i].S ; 
        node x = v0.que(l,r); 
        if(i == 0){
            r1 = x ;
        }else{
            r1 = x + r1 ;
        }
    }
    rep(i , 0, sz(vec)-1){
        int l =vec[i].F , r = vec[i].S ; 
        node x = v1.que(l,r); 
        if(i == 0){
            r2 = x ;
        }else{
            r2 = x + r2 ;
        }
    }
    if(r2.mx.F > r1.mx.F){
      //  cout << "1 " << r2.mx.S << " " << w << "<--\n" ;
        v1.upd(r2.mx.S , r2.mx.S , w) ;
    }else{
    //    cout << "0 " << r1.mx.S << " " << w << "<--\n" ;
        v0.upd(r1.mx.S , r1.mx.S , w)  ;
    } 
}

void dfs2(int v ,int p =0){
    ans[v] = v1.sm ;
    for(auto [u,w] : G[v]){
        if(u == p)continue ; 
        v1.sm = ans[v] ; 
        v1.his.clear() ;  v0.his.clear() ; 
        vector <pii> az ; az.pb({st[u],en[u]}) ;ch(az,-w) ; 
        az.clear() ;
        if(st[u] != 1)az.pb({1,st[u]-1});
        if(en[u]!=n)az.pb({en[u]+1,n});
        ch(az,w) ;
        while(v1.s[1].mn.F < v0.s[1].mx.F){
            pii a = v1.s[1].mn , b = v0.s[1].mx ;
            v0.add(a.S,a.F) ; 
            v1.add(b.S,b.F) ; 
            v1.rem(a.S) ; 
            v0.rem(b.S) ;
        }   
        vector <pair<int,node> > u1=  v1.his , u0 = v0.his ; 
        ti++ ;
        dfs2(u ,v) ; 
        while(sz(u1)) {
            int p = u1.back().F ;
            v1.s[p] =u1.back().S ; 
            u1.pop_back() ;  
        }
        while(sz(u0)) {
            int p = u0.back().F ;
            v0.s[p] =u0.back().S ; 
            u0.pop_back() ;  
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
    cin >> n >> k ;
    rep(i ,1, n-1){
        int v, u , w ;
        cin >> v >> u >> w; 
        G[v].pb({u,w});
        G[u].pb({v,w}) ; 
    }
    dfs(1) ; 
    v1.bui() ;
    rep(i ,1 ,n){
        v1.upd(st[i],st[i] , dis[i]) ; 
    }
    v0.bui() ;
    v0.vaz = 1; 
    rep(i ,1, n){
        int a = id[v1.s[1].mx.S];
        int ca = a ; 
        ll s = 0 ;
        while(a != 0){
            if(mark[a] == 1)break ;
            mark[a] =1 ;
            s += pw[a] ; 
            v1.upd(st[a],en[a] , -pw[a]) ;
            a = par[a] ;  
        } 
        v0.upd(st[ca], st[ca] , s) ; 
    }
    v1.bui() ; 
    v1.vaz = 1; 
    rep(i , 1,n)mark[i] = 0 ;
    rep(i ,1, k){
        pii a = v0.s[1].mx ;
        v0.rem(a.S) ; 
        v1.add(a.S , a.F) ;
        mark[a.S] = 1 ; 
    }
    rep(i , 1,n){
        if(mark[i] == 1)continue;
        v1.rem(i) ;
    }
    rep(i , 1 , 4*n)v1.ma[i] = v0.ma[i] =0 ; 
   // cp() ; 
   ti = 1;
    dfs2(1) ;
    rep(i ,1 ,n){
        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