Submission #626547

#TimeUsernameProblemLanguageResultExecution timeMemory
626547tamthegodPaths (RMI21_paths)C++14
19 / 100
230 ms72676 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, k; vector<pair<int, int>> adj[maxN]; int f[maxN], dp[maxN]; void ReadInput() { cin >> n >> k; for(int i=1; i<n; i++) { int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}); adj[v].pb({u, w}); } } void predfs(int u, int par) { for(auto a : adj[u]) { int v = a.fi, w = a.se; if(v == par) continue; predfs(v, u); f[u] = max(f[u], f[v] + w); } } void predfs1(int u, int par) { vector<pair<int, int>> vc; for(auto a : adj[u]) { int v = a.fi, w = a.se; if(v == par) continue; vc.pb({f[v] + w, v}); } sort(vc.begin(), vc.end(), greater<pair<int, int>>()); for(auto a : adj[u]) { int v = a.fi, w = a.se; if(v == par) continue; if(v != vc[0].se) dp[v] = max(dp[u] + w, vc[0].fi + w); else dp[v] = max(dp[u] + w, vc[1].fi + w); predfs1(v, u); } } multiset<int, greater<int>> s, s1; void dfs(int u, int par, int root) { int _max = 0, id = 0; for(auto a : adj[u]) { int v = a.fi, w = a.se; if(v == par) continue; dfs(v, u, root); if(f[v] + w > _max) { _max = f[v] + w; id = v; } } // cout << u << " " << _max << "\n"; for(auto a : adj[u]) { int v = a.fi, w = a.se; if(v == par || v == id) continue; s.insert(f[v] + w); } if(u == root) s.insert(f[u]); } int res[maxN], sum = 0; void add(int val) { auto it = s.end(); it--; if(*it < val) { sum -= *it; sum += val; s1.insert(*it); s.erase(it); s.insert(val); } else s1.insert(val); } void del(int val) { if(s.find(val) != s.end()) { sum -= val; s.erase(s.find(val)); if(s1.empty()) return; sum += *s1.begin(); s.insert(*s1.begin()); s1.erase(s1.begin()); } else s1.erase(s1.find(val)); } void reroot(int u, int par) { res[u] = sum; for(auto a : adj[u]) { int v = a.fi, w = a.se; if(v == par) continue; add(f[v]); add(dp[v]); del(f[v] + w); del(dp[v] - w); reroot(v, u); add(f[v] + w); add(dp[v] - w); del(dp[v]); del(f[v]); } } void Solve() { predfs(1, 0); predfs1(1, 0); dfs(1, 0, 1); for(int v : s) sum += v; while(s.size() > k) { auto it = s.end(); it--; sum -= *it; s1.insert(*it); s.erase(it); } reroot(1, 0); for(int i=1; i<=n; i++) cout << res[i] << '\n'; } int32_t main() { // freopen("x.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }

Compilation message (stderr)

Main.cpp: In function 'void Solve()':
Main.cpp:134:20: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  134 |     while(s.size() > k)
      |           ~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...