| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 574103 |
2022-06-07T19:17:51 Z |
urosk |
Paths (RMI21_paths) |
C++14 |
|
533 ms |
124192 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 up[maxn];
ll st[maxn][lg];
ll naj[maxn];
ll val[maxn];
ll sum[maxn];
multiset<ll> topk;
multiset<ll> other;
vector<ll> v;
ll in[maxn];
ll it = 1;
void dfs(ll u,ll par){
st[u][0] = par;
dp[u] = 0;
naj[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(dp[s]+w>dp[u]) naj[u] = naj[s];
dp[u] = max(dp[u],dp[s]+w);
}
}
bool cmp(ll x,ll y){return x>y;}
vector<ll> ch;
void dfs2(ll u,ll par){
if(sz(g[u])==1) return;
if(sz(g[u])==2&&u!=par){
for(pll p : g[u]){
ll s = p.fi;
ll w = p.sc;
if(s==par){
up[u] = up[s] + w;
}
}
for(pll p : g[u]){
ll s = p.fi;
ll w = p.sc;
if(s!=par){
dfs2(s,u);
}
}
return;
}
ch.clear();
ch.pb(up[u]);
for(pll p : g[u]){
ll s = p.fi;
ll w = p.sc;
if(s==par) continue;
ll x = dp[s] + w;
ch.pb(x);
}
sort(all(ch),cmp);
for(pll p : g[u]){
ll s = p.fi;
ll w = p.sc;
if(s==par) continue;
ll x = ch[0];
if(x==dp[s]+w) x = ch[1];
up[s] = x+w;
}
for(pll p : g[u]){
ll s = p.fi;
ll w = p.sc;
if(s==par) continue;
dfs2(s,u);
}
}
ll cur = 0;
void add(ll x){
cur+=x;
topk.insert(x);
if(sz(topk)>k){
ll y = *topk.begin();
cur-=y;
topk.erase(topk.begin());
other.insert(y);
}
}
void rem(ll x){
auto it = other.find(x);
if(it!=other.end()){
other.erase(it);
return;
}
cur-=x;
it = topk.find(x);
topk.erase(it);
if(sz(other)){
cur+=*other.rbegin();
topk.insert(*other.rbegin());
auto it = other.end();
it--;
other.erase(it);
}
}
void reshi(ll u,ll par){
ans[u] = cur;
for(pll p : g[u]){
ll s = p.fi;
ll w = p.sc;
if(s==par) continue;
add(dp[s]);
rem(dp[s]+w);
add(up[s]);
rem(up[s]-w);
reshi(s,u);
rem(dp[s]);
add(dp[s]+w);
rem(up[s]);
add(up[s]-w);
}
}
int main(){
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;
}
if(k==0){
for(ll i = 1;i<=n;i++) cout<<0<<endl;
return 0;
}
for(ll i = 1;i<=n;i++) if(sz(g[i])==1) v.pb(i);
if(n==2){
return 0;
}
if(sz(v)<=k){
for(ll i = 1;i<=n;i++) cout<<sve<<endl;
return 0;
}
ll rut = 1;
for(ll i =1;i<=n;i++) if(sz(g[i])!=1) rut = i;
up[1] = 0;
dfs(rut,rut);
dfs2(rut,rut);
ceri(up,1,n);
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(naj[st[cur][j]]==i) cur = st[cur][j];
}
val[i] = sum[i] - sum[st[cur][0]];
}
for(ll i = 1;i<=sz(v);i++) add(val[v[i-1]]);
add(0);
reshi(rut,rut);
for(ll i = 1;i<=n;i++) cout<<ans[i]<<endl;
return 0;
}
/*
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
3 1
1 2 3
2 3 4
*/
Compilation message
Main.cpp: In function 'void dfs2(long long int, long long int)':
Main.cpp:65:16: warning: unused variable 'w' [-Wunused-variable]
65 | ll w = p.sc;
| ^
Main.cpp:92:12: warning: unused variable 'w' [-Wunused-variable]
92 | ll w = p.sc;
| ^
Main.cpp: In function 'int main()':
Main.cpp:173:12: warning: unused variable 'e' [-Wunused-variable]
173 | ll e = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
48076 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
48076 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
48076 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
48076 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
533 ms |
124192 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
48076 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
