oj.uz

Submission #1038379

# Submission time Handle Problem Language Result Execution time Memory
1038379 2024-07-29T17:57:25 Z manizare Paths (RMI21_paths) C++17
100 / 100
 513 ms 253252 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39900 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 5 ms 39772 KB Output is correct
7 Correct 5 ms 39736 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39900 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 5 ms 39772 KB Output is correct
7 Correct 5 ms 39736 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 8 ms 42100 KB Output is correct
10 Correct 8 ms 40284 KB Output is correct
11 Correct 7 ms 40028 KB Output is correct
12 Correct 7 ms 40032 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39900 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 5 ms 39772 KB Output is correct
7 Correct 5 ms 39736 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 8 ms 42100 KB Output is correct
10 Correct 8 ms 40284 KB Output is correct
11 Correct 7 ms 40028 KB Output is correct
12 Correct 7 ms 40032 KB Output is correct
13 Correct 11 ms 40408 KB Output is correct
14 Correct 12 ms 44412 KB Output is correct
15 Correct 11 ms 41740 KB Output is correct
16 Correct 11 ms 40420 KB Output is correct
17 Correct 11 ms 40468 KB Output is correct
18 Correct 10 ms 41248 KB Output is correct
19 Correct 11 ms 40412 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 80672 KB Output is correct
2 Correct 450 ms 200432 KB Output is correct
3 Correct 369 ms 82800 KB Output is correct
4 Correct 351 ms 82084 KB Output is correct
5 Correct 400 ms 115744 KB Output is correct
6 Correct 387 ms 81048 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39900 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 5 ms 39772 KB Output is correct
7 Correct 5 ms 39736 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 8 ms 42100 KB Output is correct
10 Correct 8 ms 40284 KB Output is correct
11 Correct 7 ms 40028 KB Output is correct
12 Correct 7 ms 40032 KB Output is correct
13 Correct 11 ms 40408 KB Output is correct
14 Correct 12 ms 44412 KB Output is correct
15 Correct 11 ms 41740 KB Output is correct
16 Correct 11 ms 40420 KB Output is correct
17 Correct 11 ms 40468 KB Output is correct
18 Correct 10 ms 41248 KB Output is correct
19 Correct 11 ms 40412 KB Output is correct
20 Correct 354 ms 80672 KB Output is correct
21 Correct 450 ms 200432 KB Output is correct
22 Correct 369 ms 82800 KB Output is correct
23 Correct 351 ms 82084 KB Output is correct
24 Correct 400 ms 115744 KB Output is correct
25 Correct 387 ms 81048 KB Output is correct
26 Correct 436 ms 82720 KB Output is correct
27 Correct 476 ms 197792 KB Output is correct
28 Correct 513 ms 227616 KB Output is correct
29 Correct 334 ms 81348 KB Output is correct
30 Correct 423 ms 81572 KB Output is correct
31 Correct 400 ms 79132 KB Output is correct
32 Correct 473 ms 129560 KB Output is correct
33 Correct 402 ms 85240 KB Output is correct
34 Correct 361 ms 77776 KB Output is correct
35 Correct 392 ms 81824 KB Output is correct
36 Correct 512 ms 253252 KB Output is correct