oj.uz

Submission #538034

# Submission time Handle Problem Language Result Execution time Memory
538034 2022-03-16T03:36:24 Z zaneyu Paths (RMI21_paths) C++14
0 / 100
 102 ms 19360 KB 
/*input
11 3
1 2 5
2 3 3
2 6 5
3 4 4
3 5 2
1 7 6
7 8 4
7 9 5
1 10 1
10 11 1
*/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
const int maxn=1e5+5;
vector<pii> v[maxn];
int dep[maxn];
ll dist[maxn];
int k;
multiset<ll> ms;
multiset<ll,greater<ll>> ls;
ll s=0;
void add(ll x){
    ms.insert(x);
    s+=x;
    if(sz(ms)>k){
        ll z=*ms.begin();
        s-=z;
        ms.erase(ms.begin());
        ls.insert(z);
    }
}
void remove(ll x){
    auto it=ms.find(x);
    if(it==ms.end()){
        ls.erase(ls.find(x));
    }
    else{
        s-=x;
        ms.erase(it);
        if(sz(ls)){
            ll z=(*ls.begin());
            s+=z;
            ms.insert(z);
            ls.erase(ls.begin());
        }
    }
}
ll mx[maxn];
void dfs(int u,int p){
    bool hv=0;
    for(auto x:v[u]){
        if(x.f==p) continue;
        hv=1;
        dfs(x.f,u);
        remove(mx[x.f]);
        add(mx[x.f]+x.s);
        MXTO(mx[u],mx[x.f]+x.s);
    }
    if(!hv) add(0);
}
ll ans[maxn];
void dfs2(int u,int p){
    vector<pii> asd;
    asd.pb({0,u}),asd.pb({0,u});
    for(auto x:v[u]){
        asd.pb({mx[x.f]+x.s,x.f});
    }
    ans[u]=s;
    sort(ALL(asd)),reverse(ALL(asd));
    for(auto x:v[u]){
        if(x.f==p) continue;
        ll tmp=mx[u];
        mx[u]=asd[0].f;
        if(x.f==asd[0].s){
            mx[u]=asd[1].f;
        }
        remove(mx[x.f]+x.s);
        add(mx[x.f]);
        add(mx[u]+x.s);
        remove(mx[u]);
        dfs2(x.f,u);
        remove(mx[x.f]);
        add(mx[x.f]+x.s);
        remove(mx[u]+x.s);
        add(mx[u]);
        mx[u]=tmp;
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n>>k;
    REP(i,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    dfs(0,-1);
    dfs2(0,-1);
    REP(i,n) cout<<ans[i]<<'\n';
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

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