oj.uz

Submission #871030

# Submission time Handle Problem Language Result Execution time Memory
871030 2023-11-09T17:57:45 Z Ahmed57 Paths (RMI21_paths) C++17
36 / 100
 600 ms 1108 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long>> adj[2001];
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);
    }
}
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});
    }
    for(int r = 1;r<=n;r++){
        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;
            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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 13 ms 348 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Correct 12 ms 348 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 13 ms 348 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Correct 12 ms 348 KB Output is correct
8 Correct 306 ms 632 KB Output is correct
9 Correct 423 ms 676 KB Output is correct
10 Correct 422 ms 1108 KB Output is correct
11 Correct 236 ms 600 KB Output is correct
12 Correct 329 ms 908 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 13 ms 348 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Correct 12 ms 348 KB Output is correct
8 Correct 306 ms 632 KB Output is correct
9 Correct 423 ms 676 KB Output is correct
10 Correct 422 ms 1108 KB Output is correct
11 Correct 236 ms 600 KB Output is correct
12 Correct 329 ms 908 KB Output is correct
13 Execution timed out 1057 ms 1012 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 13 ms 348 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Correct 12 ms 348 KB Output is correct
8 Correct 306 ms 632 KB Output is correct
9 Correct 423 ms 676 KB Output is correct
10 Correct 422 ms 1108 KB Output is correct
11 Correct 236 ms 600 KB Output is correct
12 Correct 329 ms 908 KB Output is correct
13 Execution timed out 1057 ms 1012 KB Time limit exceeded
14 Halted 0 ms 0 KB -