oj.uz

Submission #1038354

# Submission time Handle Problem Language Result Execution time Memory
1038354 2024-07-29T17:24:41 Z manizare Paths (RMI21_paths) C++14
56 / 100
 315 ms 524288 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] ; 
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;
    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(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 ;
        his.pb({pl,s[pl]}) ;his.pb({pr,s[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){
        his.pb({p,s[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 ;
        }
        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] ;
        his.pb({p,s[p]}) ;
        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){
        his.pb({p,s[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){ 
        his.pb({p,s[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 cp(){
       rep(i , 1 , n){
            cout << max(-1ll,v1.que(i,i).mx.F) << " " ;
        }
        cout << "\n" ;
        rep(i ,1, n){
            cout << max(-1ll,v0.que(i,i).mx.F) << " " ;    
        }
        cout << "\n" ;
 
}

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 ; 
        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() ;
    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() ; 
    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) ;
    }
   // cp() ; 
    dfs2(1) ;
    rep(i ,1 ,n){
        cout << ans[i] << "\n" ;
    }
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:125:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |     for(auto [u,w] : G[v]){
      |              ^
Main.cpp: In function 'void dfs2(int, int)':
Main.cpp:177:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  177 |     for(auto [u,w] : G[v]){
      |              ^

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 4 ms 37468 KB Output is correct
3 Correct 6 ms 39636 KB Output is correct
4 Correct 7 ms 39636 KB Output is correct
5 Correct 7 ms 39644 KB Output is correct
6 Correct 7 ms 39636 KB Output is correct
7 Correct 6 ms 39636 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 4 ms 37468 KB Output is correct
3 Correct 6 ms 39636 KB Output is correct
4 Correct 7 ms 39636 KB Output is correct
5 Correct 7 ms 39644 KB Output is correct
6 Correct 7 ms 39636 KB Output is correct
7 Correct 6 ms 39636 KB Output is correct
8 Correct 16 ms 48328 KB Output is correct
9 Correct 17 ms 52420 KB Output is correct
10 Correct 17 ms 48656 KB Output is correct
11 Correct 15 ms 49096 KB Output is correct
12 Correct 17 ms 48132 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 4 ms 37468 KB Output is correct
3 Correct 6 ms 39636 KB Output is correct
4 Correct 7 ms 39636 KB Output is correct
5 Correct 7 ms 39644 KB Output is correct
6 Correct 7 ms 39636 KB Output is correct
7 Correct 6 ms 39636 KB Output is correct
8 Correct 16 ms 48328 KB Output is correct
9 Correct 17 ms 52420 KB Output is correct
10 Correct 17 ms 48656 KB Output is correct
11 Correct 15 ms 49096 KB Output is correct
12 Correct 17 ms 48132 KB Output is correct
13 Correct 28 ms 60612 KB Output is correct
14 Correct 31 ms 69056 KB Output is correct
15 Correct 27 ms 61128 KB Output is correct
16 Correct 26 ms 59848 KB Output is correct
17 Correct 26 ms 61672 KB Output is correct
18 Correct 22 ms 58056 KB Output is correct
19 Correct 26 ms 61012 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 315 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 4 ms 37468 KB Output is correct
3 Correct 6 ms 39636 KB Output is correct
4 Correct 7 ms 39636 KB Output is correct
5 Correct 7 ms 39644 KB Output is correct
6 Correct 7 ms 39636 KB Output is correct
7 Correct 6 ms 39636 KB Output is correct
8 Correct 16 ms 48328 KB Output is correct
9 Correct 17 ms 52420 KB Output is correct
10 Correct 17 ms 48656 KB Output is correct
11 Correct 15 ms 49096 KB Output is correct
12 Correct 17 ms 48132 KB Output is correct
13 Correct 28 ms 60612 KB Output is correct
14 Correct 31 ms 69056 KB Output is correct
15 Correct 27 ms 61128 KB Output is correct
16 Correct 26 ms 59848 KB Output is correct
17 Correct 26 ms 61672 KB Output is correct
18 Correct 22 ms 58056 KB Output is correct
19 Correct 26 ms 61012 KB Output is correct
20 Runtime error 315 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -