# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
534368 |
2022-03-08T06:08:08 Z |
amunduzbaev |
Paths (RMI21_paths) |
C++17 |
|
430 ms |
24240 KB |
#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 1e5 + 5;
vector<ar<int, 2>> edges[N];
int n, k, par[N][20];
long long d[N];
int tin[N], tout[N], t;
void dfs(int u, int p = -1){
tin[u] = ++t;
if(p == -1) par[u][0] = u;
for(int i=1;i<20;i++) par[u][i] = par[par[u][i-1]][i-1];
for(auto x : edges[u]){
if(x[0] == p) continue;
d[x[0]] = d[u] + x[1];
par[x[0]][0] = u;
dfs(x[0], u);
} tout[u] = t;
}
bool is(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int lca(int a, int b){
if(is(a, b)) return a;
if(is(b, a)) return b;
for(int j=19;~j;j--){
if(!is(par[a][j], b)) a = par[a][j];
} return par[a][0];
}
long long dis(int a, int b){
return d[a] + d[b] - d[lca(a, b)] * 2;
}
int a[N], vdp[N], vup[N];
long long dp[N], up[N];
void Dp(int u){
vdp[u] = u;
for(auto x : edges[u]){
if(x[0] == par[u][0]) continue;
Dp(x[0]);
if(dp[x[0]] + x[1] >= dp[u]){
dp[u] = dp[x[0]] + x[1];
vdp[u] = vdp[x[0]];
}
}
}
void redp(int u){
int tt = up[u];
int v = vup[u];
for(auto x : edges[u]){
if(x[0] == par[u][0]) continue;
if(up[x[0]] <= tt + x[1]){
up[x[0]] = tt + x[1];
vup[x[0]] = v;
}
if(tt <= dp[x[0]] + x[1]){
tt = dp[x[0]] + x[1];
v = vdp[x[0]];
}
}
reverse(edges[u].begin(), edges[u].end());
tt = 0;
v = u;
for(auto x : edges[u]){
if(x[0] == par[u][0]) continue;
if(up[x[0]] <= tt + x[1]){
up[x[0]] = tt + x[1];
vup[x[0]] = v;
}
if(tt <= dp[x[0]] + x[1]){
tt = dp[x[0]] + x[1];
v = vdp[x[0]];
}
redp(x[0]);
}
}
/*
34
34
35
39
37
39
34
38
39
38
39
28
28
28
32
30
32
28
32
32
29
30
*/
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>k;
for(int i=1;i<n;i++){
int a, b, c; cin>>a>>b>>c;
edges[a].push_back({b, c});
edges[b].push_back({a, c});
}
if(n <= 2){
int res = (n == 2 ? edges[1].back()[1] : 0);
for(int i=1;i<=n;i++) cout<<res<<"\n";
return 0;
}
int rot = -1;
for(int i=1;i<=n;i++){
if((int)edges[i].size() > 1){
rot = i;
break;
}
}
//~ assert(~rot);
dfs(rot);
Dp(rot);
vup[rot] = rot;
redp(rot);
multiset<pair<long long, int>> tot, god;
long long sum = 0;
auto upd = [&](int u, int p){
long long v = dis(a[u], u);
if(god.count({v, u})){
god.erase({v, u});
sum -= v;
if(!tot.empty()){
god.insert(*tot.rbegin()),
sum += (*tot.rbegin()).first;
tot.erase(--tot.end());
}
} tot.erase({v, u});
a[u] = p, v = dis(p, u);
god.insert({v, u});
sum += v;
if((int)god.size() > k){
tot.insert(*god.begin());
sum -= (*god.begin()).first;
god.erase(god.begin());
}
};
for(int i=1;i<=n;i++){
if((int)edges[i].size() > 1) continue;
int x = i; a[i] = i;
for(int j=19;~j;j--){
if(vdp[par[x][j]] == i) x = par[x][j];
}
x = par[x][0];
upd(i, x);
}
vector<long long> res(n + 1);
function<void(int)> dfs = [&](int u){
res[u] = sum;
for(auto x : edges[u]){
if(x[0] == par[u][0]) continue;
upd(vdp[x[0]], x[0]);
upd(vup[x[0]], x[0]);
dfs(x[0]);
upd(vdp[x[0]], u);
upd(vup[x[0]], u);
}
};
dfs(rot);
for(int i=1;i<=n;i++) cout<<res[i]<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
430 ms |
24240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |