Submission #871034

#	Time	Username	Problem	Language	Result	Execution time	Memory
871034		Ahmed57	Paths (RMI21_paths)	C++17	48 / 100	1029 ms	21336 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,bmi,bmi2")
vector<pair<int,long long>> adj[200001];
int in[2001],outt[2001];
pair<long long,long long>P[2001];int decode[2001];int timer = 0;
pair<long long,long long> seg[8001];long long lazy[8001];
void build(int p,int l,int r){
    lazy[p] = 0;
    if(l==r){
        seg[p].second = decode[l];
        seg[p].first = 0;
        return;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = max(seg[p*2],seg[p*2+1]);
}
void prop(int p,int l,int r){
    seg[p].first+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,long long val){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]+=val;
        prop(p,l,r);
        return ;
    }
    if(r<lq||l>rq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val);
    update(p*2+1,md+1,r,lq,rq,val);
    seg[p] = max(seg[p*2],seg[p*2+1]);
}
void dfs(int i,int pr){
    in[i] = ++timer;
    decode[timer] = i;
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        dfs(j.first,i);
    }
    outt[i] = timer;
}
int n;
void go(int i,int pr,long long la){
    P[i] = {pr,la};
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        update(1,1,n,in[j.first],outt[j.first],j.second);
        go(j.first,i,j.second);
    }
}
long long ma[200001],pref[200001],suf[200001];
void precalc(int i,int pr){
    ma[i] = 0;
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        precalc(j.first,i);
        ma[i] = max(ma[i],ma[j.first]+j.second);
    }
}
long long ans[200001];
void reroot(int i,int pr,long long cnt){
    ans[i] = max(ma[i],cnt);
    long long m = cnt;
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        pref[j.first] = m;
        m = max(m,ma[j.first]+j.second);
    }
    reverse(adj[i].begin(),adj[i].end());
    m = cnt;
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        suf[j.first] = m;
        m = max(m,ma[j.first]+j.second);
    }
    reverse(adj[i].begin(),adj[i].end());
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        reroot(j.first,i,max({cnt,pref[j.first],suf[j.first]})+j.second);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int k;
    cin>>n>>k;
    for(int i = 0;i<n-1;i++){
        int a,b,c;cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    if(k==1){
        precalc(1,0);
        reroot(1,0,0);
    }
    for(int r = 1;r<=n;r++){
        if(k==1){
            cout<<ans[r]<<"\n";
            continue;
        }
        timer = 0;
        dfs(r,0);
        build(1,1,n);
        go(r,0,0);
        int e = k;
        long long all = 0;
        while(e--){
            int no = seg[1].second;
            if(P[no].second==-1)break;
            while(no!=r){
                if(P[no].second==-1){
                    break;
                }
                update(1,1,n,in[no],outt[no],-P[no].second);
                all+=P[no].second;
                P[no].second = -1;
                no = P[no].first;
            }
        }
        cout<<all<<endl;
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32