Submission #1112287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112287		fryingduc	Paths (RMI21_paths)	C++17	100 / 100	208 ms	16464 KiB

Main

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

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)      
#endif
 
 const int maxn = 1e5 + 5;
int n, k;
int a[maxn];
vector<pair<int, int>> g[maxn];
long long res[maxn];
long long mx[maxn];
multiset<long long> st;
multiset<long long, greater<long long>> ot;
 
long long cur;
void insert(long long x) {
  st.insert(x);
  cur += x;
  if((int)st.size() > k) {
    cur -= *st.begin();
    ot.insert(*st.begin());
    st.erase(st.begin());
  }
}
void erase(long long x) {
  auto it = st.find(x);
  if(it != st.end()) {
    cur -= x;
    st.erase(it);
    if (!ot.empty()) {
      cur += *ot.begin();
      st.insert(*ot.begin());
      ot.erase(ot.begin());
    }
  } else {
    //if (ot.find(x) == ot.end()) return;
    ot.erase(ot.find(x));
  }
}
void dfs(int u, int prev) {
  mx[u] = 0;
  bool leaf = 1;
  for(auto e:g[u]) {
    int v = e.first, w = e.second;
    if (v == prev) continue;
    leaf = 0;
    dfs(v, u);
    erase(mx[v]);
    insert(mx[v] + w);
    mx[u] = max(mx[u], mx[v] + w);
  }
  if(leaf) {
    insert(0);
  }
}
void reroot(int u, int prev) {
  pair<long long, int> fmx = make_pair(0ll, u);
  pair<long long, int> smx = make_pair(0ll, u);
  for(auto e:g[u]) {
    int v = e.first, w = e.second;
    if(mx[v] + w >= fmx.first) {
        smx = fmx;
        fmx = make_pair(mx[v] + w, v);
    }
    else if(mx[v] + w > smx.first) {
      smx = make_pair(mx[v] + w, v);
    }
  }
  
  res[u] = cur;
  
  for(auto e:g[u]) {
    int v = e.first, w = e.second;
    if (v == prev) continue;
    insert(mx[v]);
    erase(mx[v] + w);
    long long  omx = mx[u];
    if(v == fmx.second) {
      mx[u] = smx.first;
    } else {
      mx[u] = fmx.first;
    }
    insert(mx[u] + w);
    
    if(mx[u] > 0) {
      erase(mx[u]);
    }
    
    reroot(v, u);
    
    if(mx[u] > 0) {
      insert(mx[u]);
    }
    erase(mx[u] + w);
    
    mx[u] = omx;
    insert(mx[v] + w);
    erase(mx[v]);
  }
}
void solve() {
  cin >> n >> k;
  for(int i = 1; i < n; ++i) {
    int u, v, w; cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  dfs(1, 0);
  reroot(1, 0);
  for(int i = 1; i <= n; ++i) {
    cout << res[i] << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  solve();
  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