oj.uz

답안 #871029

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871029 2023-11-09T17:57:08 Z Ahmed57 Paths (RMI21_paths) C++17
36 / 100
 600 ms 852 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 12 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 12 ms 348 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 300 ms 652 KB Output is correct
9 Correct 421 ms 852 KB Output is correct
10 Correct 406 ms 604 KB Output is correct
11 Correct 246 ms 676 KB Output is correct
12 Correct 343 ms 604 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 12 ms 348 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 300 ms 652 KB Output is correct
9 Correct 421 ms 852 KB Output is correct
10 Correct 406 ms 604 KB Output is correct
11 Correct 246 ms 676 KB Output is correct
12 Correct 343 ms 604 KB Output is correct
13 Execution timed out 1099 ms 816 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 12 ms 348 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 300 ms 652 KB Output is correct
9 Correct 421 ms 852 KB Output is correct
10 Correct 406 ms 604 KB Output is correct
11 Correct 246 ms 676 KB Output is correct
12 Correct 343 ms 604 KB Output is correct
13 Execution timed out 1099 ms 816 KB Time limit exceeded
14 Halted 0 ms 0 KB -