| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 692572 |
2023-02-02T00:37:33 Z |
moonrabbit2 |
Paths (RMI21_paths) |
C++17 |
|
100 ms |
16420 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],add[N][2],del[N][2];
int best[N];
struct DeletablePQ{
priority_queue<int,vector<int>,greater<int>> pq1,pq2;
void add(int x){
pq1.emplace(x);
}
void del(int x){
pq2.emplace(x);
}
int 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(int 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(int v){
if(TopK.top()>v){
Left.del(-v);
return;
}
Ksum-=v;
TopK.del(v);
int 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,dp[u]));
} else{
insertVal(dp[v]);
insertVal(max(cur,dp[u])+c);
deleteVal(dp[v]+c);
deleteVal(max(cur,dp[u]));
}
dfs2(v,u,cur+c);
if(v==best[u]){
insertVal(dp[v]+c);
insertVal(max(cur,dp[u]));
deleteVal(dp[v]);
deleteVal(max(cur,scd[u])+c);
} else{
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,dp[1]);
for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
16420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
