oj.uz

Submission #871027

# Submission time Handle Problem Language Result Execution time Memory
871027 2023-11-09T17:54:38 Z Ahmed57 Paths (RMI21_paths) C++17
19 / 100
 435 ms 700 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==0){
                    break;
                }
                update(1,1,n,in[no],outt[no],-P[no].second);
                all+=P[no].second;
                P[no].second = 0;
                no = P[no].first;
            }
        }
        cout<<all<<endl;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 348 KB Output is correct
4 Correct 14 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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 348 KB Output is correct
4 Correct 14 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 296 ms 664 KB Output is correct
9 Correct 435 ms 700 KB Output is correct
10 Incorrect 319 ms 600 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 348 KB Output is correct
4 Correct 14 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 296 ms 664 KB Output is correct
9 Correct 435 ms 700 KB Output is correct
10 Incorrect 319 ms 600 KB Output isn't correct
11 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 348 KB Output is correct
4 Correct 14 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 296 ms 664 KB Output is correct
9 Correct 435 ms 700 KB Output is correct
10 Incorrect 319 ms 600 KB Output isn't correct
11 Halted 0 ms 0 KB -