oj.uz

Submission #574066

# Submission time Handle Problem Language Result Execution time Memory
574066 2022-06-07T16:41:34 Z urosk Paths (RMI21_paths) C++14
56 / 100
 600 ms 42004 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 13
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 23800 KB Output is correct
2 Correct 16 ms 23892 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Output is correct
2 Correct 16 ms 23892 KB Output is correct
3 Correct 15 ms 23764 KB Output is correct
4 Correct 17 ms 23880 KB Output is correct
5 Correct 17 ms 23872 KB Output is correct
6 Correct 14 ms 23820 KB Output is correct
7 Correct 16 ms 23880 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Output is correct
2 Correct 16 ms 23892 KB Output is correct
3 Correct 15 ms 23764 KB Output is correct
4 Correct 17 ms 23880 KB Output is correct
5 Correct 17 ms 23872 KB Output is correct
6 Correct 14 ms 23820 KB Output is correct
7 Correct 16 ms 23880 KB Output is correct
8 Correct 112 ms 24020 KB Output is correct
9 Correct 101 ms 24068 KB Output is correct
10 Correct 97 ms 24048 KB Output is correct
11 Correct 112 ms 24032 KB Output is correct
12 Correct 92 ms 24040 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Output is correct
2 Correct 16 ms 23892 KB Output is correct
3 Correct 15 ms 23764 KB Output is correct
4 Correct 17 ms 23880 KB Output is correct
5 Correct 17 ms 23872 KB Output is correct
6 Correct 14 ms 23820 KB Output is correct
7 Correct 16 ms 23880 KB Output is correct
8 Correct 112 ms 24020 KB Output is correct
9 Correct 101 ms 24068 KB Output is correct
10 Correct 97 ms 24048 KB Output is correct
11 Correct 112 ms 24032 KB Output is correct
12 Correct 92 ms 24040 KB Output is correct
13 Correct 421 ms 24224 KB Output is correct
14 Correct 422 ms 24340 KB Output is correct
15 Correct 355 ms 24284 KB Output is correct
16 Correct 446 ms 24268 KB Output is correct
17 Correct 393 ms 24364 KB Output is correct
18 Correct 249 ms 24176 KB Output is correct
19 Correct 414 ms 24380 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 42004 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 23800 KB Output is correct
2 Correct 16 ms 23892 KB Output is correct
3 Correct 15 ms 23764 KB Output is correct
4 Correct 17 ms 23880 KB Output is correct
5 Correct 17 ms 23872 KB Output is correct
6 Correct 14 ms 23820 KB Output is correct
7 Correct 16 ms 23880 KB Output is correct
8 Correct 112 ms 24020 KB Output is correct
9 Correct 101 ms 24068 KB Output is correct
10 Correct 97 ms 24048 KB Output is correct
11 Correct 112 ms 24032 KB Output is correct
12 Correct 92 ms 24040 KB Output is correct
13 Correct 421 ms 24224 KB Output is correct
14 Correct 422 ms 24340 KB Output is correct
15 Correct 355 ms 24284 KB Output is correct
16 Correct 446 ms 24268 KB Output is correct
17 Correct 393 ms 24364 KB Output is correct
18 Correct 249 ms 24176 KB Output is correct
19 Correct 414 ms 24380 KB Output is correct
20 Execution timed out 1086 ms 42004 KB Time limit exceeded
21 Halted 0 ms 0 KB -