oj.uz

답안 #1038347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1038347 2024-07-29T17:15:05 Z manizare Paths (RMI21_paths) C++14
56 / 100
 406 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 <int,int>
#define PII pair<pii , pii>
#define ld long double 
#define int 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 int 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] , dis[maxn] , ans[maxn]   ; 
vector <pii> G[maxn] ; 
struct node{
    pii mx , mn ;
    int 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] ; int sm =0 , ok =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 , w = s[p].lz ,pr =p<<1|1 ;
        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 , int 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 ,int 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 ; 
        int 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 ; 
    }
    v1.ok = 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(long long int, long long int)':
Main.cpp:123:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |     for(auto [u,w] : G[v]){
      |              ^
Main.cpp: In function 'void dfs2(long long int, long long int)':
Main.cpp:175:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  175 |     for(auto [u,w] : G[v]){
      |              ^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39628 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39628 KB Output is correct
3 Correct 8 ms 41684 KB Output is correct
4 Correct 6 ms 41796 KB Output is correct
5 Correct 6 ms 41680 KB Output is correct
6 Correct 7 ms 41752 KB Output is correct
7 Correct 6 ms 41684 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39628 KB Output is correct
3 Correct 8 ms 41684 KB Output is correct
4 Correct 6 ms 41796 KB Output is correct
5 Correct 6 ms 41680 KB Output is correct
6 Correct 7 ms 41752 KB Output is correct
7 Correct 6 ms 41684 KB Output is correct
8 Correct 14 ms 49904 KB Output is correct
9 Correct 16 ms 55240 KB Output is correct
10 Correct 16 ms 50372 KB Output is correct
11 Correct 15 ms 49608 KB Output is correct
12 Correct 16 ms 50376 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39628 KB Output is correct
3 Correct 8 ms 41684 KB Output is correct
4 Correct 6 ms 41796 KB Output is correct
5 Correct 6 ms 41680 KB Output is correct
6 Correct 7 ms 41752 KB Output is correct
7 Correct 6 ms 41684 KB Output is correct
8 Correct 14 ms 49904 KB Output is correct
9 Correct 16 ms 55240 KB Output is correct
10 Correct 16 ms 50372 KB Output is correct
11 Correct 15 ms 49608 KB Output is correct
12 Correct 16 ms 50376 KB Output is correct
13 Correct 26 ms 62136 KB Output is correct
14 Correct 29 ms 71352 KB Output is correct
15 Correct 26 ms 64188 KB Output is correct
16 Correct 22 ms 63168 KB Output is correct
17 Correct 25 ms 62404 KB Output is correct
18 Correct 20 ms 59336 KB Output is correct
19 Correct 25 ms 61888 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 406 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 39516 KB Output is correct
2 Correct 5 ms 39628 KB Output is correct
3 Correct 8 ms 41684 KB Output is correct
4 Correct 6 ms 41796 KB Output is correct
5 Correct 6 ms 41680 KB Output is correct
6 Correct 7 ms 41752 KB Output is correct
7 Correct 6 ms 41684 KB Output is correct
8 Correct 14 ms 49904 KB Output is correct
9 Correct 16 ms 55240 KB Output is correct
10 Correct 16 ms 50372 KB Output is correct
11 Correct 15 ms 49608 KB Output is correct
12 Correct 16 ms 50376 KB Output is correct
13 Correct 26 ms 62136 KB Output is correct
14 Correct 29 ms 71352 KB Output is correct
15 Correct 26 ms 64188 KB Output is correct
16 Correct 22 ms 63168 KB Output is correct
17 Correct 25 ms 62404 KB Output is correct
18 Correct 20 ms 59336 KB Output is correct
19 Correct 25 ms 61888 KB Output is correct
20 Runtime error 406 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -