oj.uz

Submission #692590

# Submission time Handle Problem Language Result Execution time Memory
692590 2023-02-02T00:53:37 Z moonrabbit2 Paths (RMI21_paths) C++17
8 / 100
 104 ms 17384 KB 
#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,cur+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,cur+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]);
	ans[1]=Ksum;
	for(auto [v,c]: g[1]){
		if(v==best[1]){
			insertVal(dp[v]);
			insertVal(scd[1]+c);
			deleteVal(dp[v]+c);
			deleteVal(scd[1]);
			dfs2(v,1,scd[1]+c);
			insertVal(dp[v]+c);
			insertVal(scd[1]);
			deleteVal(dp[v]);
			deleteVal(scd[1]+c);
		} else{
			insertVal(dp[v]);
			insertVal(dp[1]+c);
			deleteVal(dp[v]+c);
			deleteVal(dp[1]);
			dfs2(v,1,dp[1]+c);
			insertVal(dp[v]+c);
			insertVal(dp[1]);
			deleteVal(dp[v]);
			deleteVal(dp[1]+c);
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 17384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -