Submission #534372

#	Time	Username	Problem	Language	Result	Execution time	Memory
534372		amunduzbaev	Paths (RMI21_paths)	C++17	100 / 100	453 ms	27452 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long i64;
const int N = 1e5 + 5;
vector<ar<int, 2>> edges[N];
int n, k, par[N][20];
int tin[N], tout[N], t;
i64 d[N];

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];
}

i64 dis(int a, int b){
	return d[a] + d[b] - d[lca(a, b)] * 2;
}

int a[N], vdp[N], vup[N];
i64 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){
	i64 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<i64, int>> tot, god;
	i64 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<i64> 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";
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32