oj.uz

Submission #1038376

# Submission time Handle Problem Language Result Execution time Memory
1038376 2024-07-29T17:53:45 Z manizare Paths (RMI21_paths) C++17
68 / 100
 600 ms 285216 KB 
#include <bits/stdc++.h>
 

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2") 
#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] ;
    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 ;
        }
        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) ;
        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() ;
    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) ;
    }
    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 39512 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 39512 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 6 ms 39636 KB Output is correct
4 Correct 5 ms 39772 KB Output is correct
5 Correct 6 ms 39516 KB Output is correct
6 Correct 5 ms 39768 KB Output is correct
7 Correct 5 ms 39516 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39512 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 6 ms 39636 KB Output is correct
4 Correct 5 ms 39772 KB Output is correct
5 Correct 6 ms 39516 KB Output is correct
6 Correct 5 ms 39768 KB Output is correct
7 Correct 5 ms 39516 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 9 ms 42660 KB Output is correct
10 Correct 9 ms 40536 KB Output is correct
11 Correct 8 ms 40024 KB Output is correct
12 Correct 8 ms 40284 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39512 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 6 ms 39636 KB Output is correct
4 Correct 5 ms 39772 KB Output is correct
5 Correct 6 ms 39516 KB Output is correct
6 Correct 5 ms 39768 KB Output is correct
7 Correct 5 ms 39516 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 9 ms 42660 KB Output is correct
10 Correct 9 ms 40536 KB Output is correct
11 Correct 8 ms 40024 KB Output is correct
12 Correct 8 ms 40284 KB Output is correct
13 Correct 12 ms 40408 KB Output is correct
14 Correct 13 ms 46104 KB Output is correct
15 Correct 12 ms 42332 KB Output is correct
16 Correct 11 ms 40424 KB Output is correct
17 Correct 11 ms 40472 KB Output is correct
18 Correct 13 ms 41504 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 421 ms 81776 KB Output is correct
2 Correct 564 ms 247840 KB Output is correct
3 Correct 417 ms 83636 KB Output is correct
4 Correct 456 ms 80860 KB Output is correct
5 Correct 504 ms 128908 KB Output is correct
6 Correct 420 ms 80620 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39512 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 6 ms 39636 KB Output is correct
4 Correct 5 ms 39772 KB Output is correct
5 Correct 6 ms 39516 KB Output is correct
6 Correct 5 ms 39768 KB Output is correct
7 Correct 5 ms 39516 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 9 ms 42660 KB Output is correct
10 Correct 9 ms 40536 KB Output is correct
11 Correct 8 ms 40024 KB Output is correct
12 Correct 8 ms 40284 KB Output is correct
13 Correct 12 ms 40408 KB Output is correct
14 Correct 13 ms 46104 KB Output is correct
15 Correct 12 ms 42332 KB Output is correct
16 Correct 11 ms 40424 KB Output is correct
17 Correct 11 ms 40472 KB Output is correct
18 Correct 13 ms 41504 KB Output is correct
19 Correct 11 ms 40412 KB Output is correct
20 Correct 421 ms 81776 KB Output is correct
21 Correct 564 ms 247840 KB Output is correct
22 Correct 417 ms 83636 KB Output is correct
23 Correct 456 ms 80860 KB Output is correct
24 Correct 504 ms 128908 KB Output is correct
25 Correct 420 ms 80620 KB Output is correct
26 Correct 480 ms 79900 KB Output is correct
27 Correct 561 ms 243676 KB Output is correct
28 Execution timed out 605 ms 285216 KB Time limit exceeded
29 Halted 0 ms 0 KB -