Submission #692591

#	Time	Username	Problem	Language	Result	Execution time	Memory
692591		moonrabbit2	Paths (RMI21_paths)	C++17	100 / 100	210 ms	23500 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5;
int n,k,m;
vector<array<int,2>> g[N];
ll dp[N],scd[N],vals[N];
int best[N];
struct DeletablePQ{
	priority_queue<ll,vector<ll>,greater<ll>> pq1,pq2;
	void add(ll x){
		pq1.emplace(x);
	}
	void del(ll x){
		pq2.emplace(x);
	}
	ll top(){
		assert(pq1.size()>pq2.size());
		while(pq2.size()&&pq1.top()==pq2.top()){
			pq1.pop();
			pq2.pop();
		}
		return pq1.top();
	}
}TopK,Left;
ll Ksum,ans[N];
void dfs(int u,int p){
	for(auto [v,c]: g[u]) if(p!=v){
		dfs(v,u);
		if(dp[v]+c<dp[u]) vals[++m]=dp[v]+c;
		else{
			if(dp[u]) vals[++m]=dp[u];
			dp[u]=dp[v]+c;
			best[u]=v;
		}
	}
	for(auto [v,c]: g[u]) if(p!=v&&best[u]!=v){
		scd[u]=max(scd[u],dp[v]+c);
	}
}
void insertVal(ll v){
	if(TopK.top()>=v){
		Left.add(-v);
		return;
	}
	Ksum+=v-TopK.top();
	Left.add(-TopK.top());
	TopK.del(TopK.top());
	TopK.add(v);
}
void deleteVal(ll v){
	if(TopK.top()>v){
		Left.del(-v);
		return;
	}
	Ksum-=v;
	TopK.del(v);
	ll val=-Left.top();
	Ksum+=val;
	Left.del(-val);
	TopK.add(val);
}
void dfs2(int u,int p,ll cur){
	ans[u]=Ksum;
	for(auto [v,c]: g[u]) if(p!=v){
		if(v==best[u]){
			insertVal(dp[v]);
			insertVal(max(cur,scd[u])+c);
			deleteVal(dp[v]+c);
			deleteVal(max(cur,scd[u]));
			dfs2(v,u,max(cur,scd[u])+c);
			insertVal(dp[v]+c);
			insertVal(max(cur,scd[u]));
			deleteVal(dp[v]);
			deleteVal(max(cur,scd[u])+c);
		} else{
			insertVal(dp[v]);
			insertVal(max(cur,dp[u])+c);
			deleteVal(dp[v]+c);
			deleteVal(max(cur,dp[u]));
			dfs2(v,u,max(cur,dp[u])+c);
			insertVal(dp[v]+c);
			insertVal(max(cur,dp[u]));
			deleteVal(dp[v]);
			deleteVal(max(cur,dp[u])+c);
		}
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k;
	for(int u,v,c,i=1;i<n;i++){
		cin>>u>>v>>c;
		g[u].push_back({v,c});
		g[v].push_back({u,c});
	}
	dfs(1,0);
	vals[++m]=dp[1];
	sort(vals+1,vals+1+m,greater<>());
	for(int i=1;i<=k;i++){
		TopK.add(vals[i]);
		Ksum+=vals[i];
	}
	for(int i=k+1;i<=n;i++) Left.add(-vals[i]);
	dfs2(1,0,0);
	for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
	return 0;
}

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