Submission #1127926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127926		pokmui9909	Paths (RMI21_paths)	C++20	8 / 100	1095 ms	11056 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second

ll N, K, Sum = 0;
priority_queue<ll, vector<ll>, greater<ll>> Q1;
priority_queue<ll, vector<ll>, greater<ll>> E1;
priority_queue<ll> Q2;
priority_queue<ll> E2;

void Clean(){
	while(!E1.empty() && E1.top() == Q1.top()) E1.pop(), Q1.pop();
	while(!E2.empty() && E2.top() == Q2.top()) E2.pop(), Q2.pop();
}
void Add(ll v){
	Clean();
	if(Q1.size() < K){
		Q1.push(v);
		Sum += v;
	} else {
		Q2.push(v);
	}
	while(!Q1.empty() && !Q2.empty()){
		ll f1 = Q1.top(), f2 = Q2.top();
		if(f1 >= f2) break;
		Q1.pop(); Q2.pop();
		Sum += f2 - f1;
		Q1.push(f2); Q2.push(f1);
	}
}
void Del(ll v){
	Clean();
	if(!Q2.empty() && v <= Q2.top()){
		E2.push(v);
	} else {
		E1.push(v);
		Sum += -v + Q2.top();
		Q1.push(Q2.top());
		Q2.pop();
	}
}

ll Rt, D[100005], Sec[100005], F[100005], Go[100005], Ans[100005];
vector<pair<ll, ll>> T[100005];

void cal(ll u, ll p){
	for(auto e : T[u]){
		if(e.x == p) continue;
		cal(e.x, u);
		if(D[u] < D[e.x] + e.y){
			Sec[u] = D[u], D[u] = D[e.x] + e.y;
			Go[u] = e.x;
		} else if(Sec[u] < D[e.x] + e.y){
			Sec[u] = D[e.x] + e.y;
		}
	}
	for(auto e : T[u]){
		if(e.x == p) continue;
		if(e.x == Go[u]){
			F[e.x] = max(F[u], Sec[u]) + e.y;
		} else {
			F[e.x] = max(F[u], D[u]) + e.y;
		}
		cal(e.x, u);
	}
}
void init(ll u, ll p, ll d){
	if(T[u].size() == 1){
		Add(d); return;
	}
	for(auto e : T[u]){
		if(e.x == p) continue;
		if(e.x == Go[u]){
			init(e.x, u, d + e.y);
		} else {
			init(e.x, u, e.y);
		}
	}
}
void dfs(ll u, ll p){
	Ans[u] = Sum;
	for(auto e : T[u]){
		if(e.x == p) continue;
		if(e.x == Go[u]){
			ll up = max(Sec[u], F[u]);
			Del(D[u]); Add(D[u] - e.y);
			Del(up); Add(up + e.y);

			dfs(e.x, u);

			Add(D[u]); Del(D[u] - e.y);
			Add(up); Del(up + e.y);
		} else {
			ll up = max(D[u], F[u]);
			Del(up); Add(up + e.y);
			Del(D[e.x] + e.y); Add(D[e.x]);

			dfs(e.x, u);

			Add(up); Del(up + e.y);
			Add(D[e.x] + e.y); Del(D[e.x]);
		}
	}
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> N >> K;
	for(ll i = 1; i < N; i++){
		ll u, v, c; cin >> u >> v >> c;
		T[u].push_back({v, c});
		T[v].push_back({u, c});
	}
	Rt = 1;
	while(T[Rt].size() == 1) Rt++;
	cal(Rt, -1);
	init(Rt, -1, 0);
	dfs(1, -1);
	for(ll i = 1; i <= N; i++){
		cout << Ans[i] << '\n';
	}
}

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