oj.uz

Submission #1038374

# Submission time Handle Problem Language Result Execution time Memory
1038374 2024-07-29T17:52:33 Z manizare Paths (RMI21_paths) C++14
68 / 100
 600 ms 289308 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] ;
    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" ;
    }
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39512 KB Output is correct
2 Correct 4 ms 39512 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 4 ms 39512 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39772 KB Output is correct
5 Correct 5 ms 39524 KB Output is correct
6 Correct 5 ms 39768 KB Output is correct
7 Correct 5 ms 39780 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 4 ms 39512 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39772 KB Output is correct
5 Correct 5 ms 39524 KB Output is correct
6 Correct 5 ms 39768 KB Output is correct
7 Correct 5 ms 39780 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 11 ms 42728 KB Output is correct
10 Correct 8 ms 40532 KB Output is correct
11 Correct 7 ms 40028 KB Output is correct
12 Correct 8 ms 40280 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 4 ms 39512 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39772 KB Output is correct
5 Correct 5 ms 39524 KB Output is correct
6 Correct 5 ms 39768 KB Output is correct
7 Correct 5 ms 39780 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 11 ms 42728 KB Output is correct
10 Correct 8 ms 40532 KB Output is correct
11 Correct 7 ms 40028 KB Output is correct
12 Correct 8 ms 40280 KB Output is correct
13 Correct 12 ms 40412 KB Output is correct
14 Correct 14 ms 46076 KB Output is correct
15 Correct 12 ms 42340 KB Output is correct
16 Correct 11 ms 40240 KB Output is correct
17 Correct 11 ms 40472 KB Output is correct
18 Correct 10 ms 41504 KB Output is correct
19 Correct 11 ms 40436 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 82996 KB Output is correct
2 Correct 570 ms 250924 KB Output is correct
3 Correct 423 ms 82608 KB Output is correct
4 Correct 437 ms 84664 KB Output is correct
5 Correct 523 ms 130140 KB Output is correct
6 Correct 399 ms 84892 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 4 ms 39512 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39772 KB Output is correct
5 Correct 5 ms 39524 KB Output is correct
6 Correct 5 ms 39768 KB Output is correct
7 Correct 5 ms 39780 KB Output is correct
8 Correct 8 ms 40028 KB Output is correct
9 Correct 11 ms 42728 KB Output is correct
10 Correct 8 ms 40532 KB Output is correct
11 Correct 7 ms 40028 KB Output is correct
12 Correct 8 ms 40280 KB Output is correct
13 Correct 12 ms 40412 KB Output is correct
14 Correct 14 ms 46076 KB Output is correct
15 Correct 12 ms 42340 KB Output is correct
16 Correct 11 ms 40240 KB Output is correct
17 Correct 11 ms 40472 KB Output is correct
18 Correct 10 ms 41504 KB Output is correct
19 Correct 11 ms 40436 KB Output is correct
20 Correct 458 ms 82996 KB Output is correct
21 Correct 570 ms 250924 KB Output is correct
22 Correct 423 ms 82608 KB Output is correct
23 Correct 437 ms 84664 KB Output is correct
24 Correct 523 ms 130140 KB Output is correct
25 Correct 399 ms 84892 KB Output is correct
26 Correct 503 ms 83468 KB Output is correct
27 Correct 533 ms 246492 KB Output is correct
28 Correct 576 ms 289308 KB Output is correct
29 Correct 428 ms 83824 KB Output is correct
30 Correct 484 ms 83568 KB Output is correct
31 Correct 440 ms 81780 KB Output is correct
32 Execution timed out 630 ms 153040 KB Time limit exceeded
33 Halted 0 ms 0 KB -