oj.uz

Submission #871034

# Submission time Handle Problem Language Result Execution time Memory
871034 2023-11-09T18:11:55 Z Ahmed57 Paths (RMI21_paths) C++17
48 / 100
 600 ms 21336 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 10 ms 7256 KB Output is correct
4 Correct 15 ms 7260 KB Output is correct
5 Correct 8 ms 7256 KB Output is correct
6 Correct 14 ms 7260 KB Output is correct
7 Correct 13 ms 7260 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 10 ms 7256 KB Output is correct
4 Correct 15 ms 7260 KB Output is correct
5 Correct 8 ms 7256 KB Output is correct
6 Correct 14 ms 7260 KB Output is correct
7 Correct 13 ms 7260 KB Output is correct
8 Correct 267 ms 7416 KB Output is correct
9 Correct 378 ms 7496 KB Output is correct
10 Correct 366 ms 7260 KB Output is correct
11 Correct 214 ms 7764 KB Output is correct
12 Correct 293 ms 7256 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 10 ms 7256 KB Output is correct
4 Correct 15 ms 7260 KB Output is correct
5 Correct 8 ms 7256 KB Output is correct
6 Correct 14 ms 7260 KB Output is correct
7 Correct 13 ms 7260 KB Output is correct
8 Correct 267 ms 7416 KB Output is correct
9 Correct 378 ms 7496 KB Output is correct
10 Correct 366 ms 7260 KB Output is correct
11 Correct 214 ms 7764 KB Output is correct
12 Correct 293 ms 7256 KB Output is correct
13 Execution timed out 1029 ms 7480 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 19956 KB Output is correct
2 Correct 53 ms 21336 KB Output is correct
3 Correct 48 ms 19792 KB Output is correct
4 Correct 46 ms 19788 KB Output is correct
5 Correct 60 ms 20516 KB Output is correct
6 Correct 68 ms 19780 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 10 ms 7256 KB Output is correct
4 Correct 15 ms 7260 KB Output is correct
5 Correct 8 ms 7256 KB Output is correct
6 Correct 14 ms 7260 KB Output is correct
7 Correct 13 ms 7260 KB Output is correct
8 Correct 267 ms 7416 KB Output is correct
9 Correct 378 ms 7496 KB Output is correct
10 Correct 366 ms 7260 KB Output is correct
11 Correct 214 ms 7764 KB Output is correct
12 Correct 293 ms 7256 KB Output is correct
13 Execution timed out 1029 ms 7480 KB Time limit exceeded
14 Halted 0 ms 0 KB -