oj.uz

Submission #574065

# Submission time Handle Problem Language Result Execution time Memory
574065 2022-06-07T16:40:53 Z urosk Paths (RMI21_paths) C++14
36 / 100
 600 ms 58964 KB 
//https://oj.uz/problem/view/RMI21_paths
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 1000005
#define lg 32
ll n,k;
vector<pll> g[maxn];
ll ans[maxn];
ll dp[maxn];
ll st[maxn][lg];
ll val[maxn];
ll sum[maxn];
vector<ll> v;
void dfs(ll u,ll par){
    st[u][0] = par;
    dp[u] = u;
    for(pll p : g[u]){
        ll s = p.fi;
        ll w = p.sc;
        if(s==par) continue;
        sum[s] = sum[u] + w;
        dfs(s,u);
        if(sum[dp[u]] - sum[u]<sum[dp[s]] - sum[s] + w) dp[u] = dp[s];
    }
}
bool cmp(ll x,ll y){return val[x]>val[y];}
void reshi(ll rut){
    sum[rut] = 0;
    dfs(rut,rut);
    for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[i][j] = st[st[i][j-1]][j-1];
    for(ll i = 1;i<=n;i++){
        ll e = 0;
        ll cur = i;
        for(ll j = lg-1;j>=0;j--){
            if(dp[st[cur][j]]==i) cur = st[cur][j];
        }
        val[i] = sum[i] - sum[st[cur][0]];
    }
    sort(all(v),cmp);
    for(ll i = 1;i<=k;i++) ans[rut]+=val[v[i-1]];
}
int main(){
	daj_mi_malo_vremena
    cin >> n >> k;
    ll sve = 0;
    for(ll i = 1;i<=n-1;i++){
        ll x,y,w; cin >> x >> y >> w;
        g[x].pb({y,w});
        g[y].pb({x,w});
        sve+=w;
    }
    for(ll i = 1;i<=n;i++) if(sz(g[i])==1) v.pb(i);
    if(sz(v)<=k){
        for(ll i = 1;i<=n;i++) cout<<sve<<endl;
        return 0;
    }
    for(ll i = 1;i<=n;i++) reshi(i);
    for(ll i = 1;i<=n;i++) cout<<ans[i]<<endl;
	return 0;
}

Compilation message

Main.cpp: In function 'void reshi(long long int)':
Main.cpp:49:12: warning: unused variable 'e' [-Wunused-variable]
   49 |         ll e = 0;
      |            ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23836 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23836 KB Output is correct
3 Correct 18 ms 23892 KB Output is correct
4 Correct 19 ms 23876 KB Output is correct
5 Correct 20 ms 23900 KB Output is correct
6 Correct 19 ms 23836 KB Output is correct
7 Correct 18 ms 23892 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23836 KB Output is correct
3 Correct 18 ms 23892 KB Output is correct
4 Correct 19 ms 23876 KB Output is correct
5 Correct 20 ms 23900 KB Output is correct
6 Correct 19 ms 23836 KB Output is correct
7 Correct 18 ms 23892 KB Output is correct
8 Correct 185 ms 24176 KB Output is correct
9 Correct 180 ms 24352 KB Output is correct
10 Correct 175 ms 24204 KB Output is correct
11 Correct 194 ms 24180 KB Output is correct
12 Correct 179 ms 24200 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23836 KB Output is correct
3 Correct 18 ms 23892 KB Output is correct
4 Correct 19 ms 23876 KB Output is correct
5 Correct 20 ms 23900 KB Output is correct
6 Correct 19 ms 23836 KB Output is correct
7 Correct 18 ms 23892 KB Output is correct
8 Correct 185 ms 24176 KB Output is correct
9 Correct 180 ms 24352 KB Output is correct
10 Correct 175 ms 24204 KB Output is correct
11 Correct 194 ms 24180 KB Output is correct
12 Correct 179 ms 24200 KB Output is correct
13 Execution timed out 749 ms 24540 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 58964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23836 KB Output is correct
3 Correct 18 ms 23892 KB Output is correct
4 Correct 19 ms 23876 KB Output is correct
5 Correct 20 ms 23900 KB Output is correct
6 Correct 19 ms 23836 KB Output is correct
7 Correct 18 ms 23892 KB Output is correct
8 Correct 185 ms 24176 KB Output is correct
9 Correct 180 ms 24352 KB Output is correct
10 Correct 175 ms 24204 KB Output is correct
11 Correct 194 ms 24180 KB Output is correct
12 Correct 179 ms 24200 KB Output is correct
13 Execution timed out 749 ms 24540 KB Time limit exceeded
14 Halted 0 ms 0 KB -