Submission #873475

#TimeUsernameProblemLanguageResultExecution timeMemory
873475sleepntsheepPaths (RMI21_paths)C++17
12 / 100
71 ms17760 KiB
#include <cstdio> #include <cstring> #include <cassert> #include <string> #include <deque> #include <vector> #include <map> #include <queue> #include <algorithm> #include <iostream> #include <utility> using namespace std; using ll = long long; using ld = long double; #define ShinLena cin.tie(nullptr)->sync_with_stdio(false) #define N 200005 #define ALL(x) x.begin(), x.end() int n, k; vector<pair<int, int>> g[N]; namespace sub123 { ll dp[1001][101]; int sz[N]; void dfs1(int u, int p) { dp[u][0] = dp[u][1] = 0; sz[u] = 1; for (auto [w, v] : g[u]) if (v != p) { dfs1(v, u); for (int i = sz[u]; i >= 0; --i) for (int j = 1; i+j <= k && j <= sz[v]; ++j) dp[u][i+j] = max(dp[u][i+j], dp[u][i] + dp[v][j] + w); sz[u] += sz[v]; } } ll oneroot(int u) { memset(dp, 0xbf, sizeof dp); dfs1(u, u); return dp[u][k]; } }; namespace sub5 { ll dp2[N], dp3[N], dp4[N]; void dfs2(int u, int p) { dp2[u] = 0; for (auto [w, v] : g[u]) if (v != p) { dfs2(v, u); if (dp2[v] + w >= dp2[u]) dp3[u] = dp2[u], dp2[u] = dp2[v] + w; else if (dp2[v] + w >= dp3[u]) dp3[u] = dp2[v] + w; } } void dfs3(int u, int p) { for (auto [w, v] : g[u]) if (v != p) { if (dp2[v] + w == dp2[u]) dp4[v] = max(dp4[u] + w, dp3[u] + w); else dp4[v] = max(dp4[u] + w, dp2[u] + w); dfs3(v, u); } } }; namespace sub4 { int tin[2001], tout[2001], timer, P[2001][2], rv[2001]; ll rt[N]{0}; struct segtree { pair<ll, int> t[4005]; ll lz[4005]{0}; segtree() { } void build(int v, int l, int r) { if (l >= r) { int u = rv[l]; lz[v]=0; if (tin[u]==tout[u]) t[v] = {rt[u], u}; else t[v] = {-1e17,u}; return; } int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2; build(vl,l,m),build(vr,m+1,r); t[v]=max(t[vl],t[vr]); } void push(int v, int l, int r) { if (!lz[v])return; if (t[v].first>-1e17)t[v].first+=lz[v]; if(l-r) { int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2; lz[vl]+=lz[v];lz[vr]+=lz[v]; } lz[v]=0; } pair<ll, int> qry(int x, int y, int v, int l, int r) { push(v,l,r); if (y<l||r<x) return {-1e18, -1e9}; if (x<=l&&r<=y){return t[v];} int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2; return max(qry(x, y, vl,l,m),qry(x,y,vr,m+1,r)); } void upd(int x, int y, int k, int v, int l, int r) { push(v,l,r); if (y<l||r<x) return; if (x<=l&&r<=y){lz[v]=k;push(v,l,r);return;} int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2; upd(x, y,k,vl,l,m),upd(x,y,k,vr,m+1,r); t[v]=max(t[vl],t[vr]); } } t; void dfs1(int u, int p) { rv[tin[u] = timer++] = u; for (auto [w, v] : g[u]) if (v-p) P[v][0]=u,P[v][1]=w,rt[v]=rt[u]+w,dfs1(v, u); tout[u] = timer - 1; } ll ans; int del[2010]{0}; void process() { pair<ll,int> x = t.qry(0,n-1,0,0,n-1); ans += x.first; for (int c = x.second; c; c = P[c][0]) { int p = P[c][0], w = P[c][1]; if(!del[c]) t.upd(tin[c], tout[c], -w, 0, 0, n-1),del[c]=1; } } ll oneroot(int root) { memset(rt,0,sizeof rt); memset(del,0,sizeof del); memset(P,0,sizeof P); rt[root]=ans=timer=0; dfs1(root,root); t.build(0,0,n-1); for (int i = 1; i <= k; ++i) process(); return ans; } }; int main() { ShinLena; cin >> n >> k; for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u); if (k == 1) { sub5::dfs2(1, 1); sub5::dfs3(1, 1); for (int i = 1; i <= n; ++i) cout << max(sub5::dp2[i], sub5::dp4[i]) << '\n'; } else if (n <= 2000) { for (int i = 1; i <= n; ++i) cout << sub4::oneroot(i) << '\n'; } else if (n <= 1002) { for (int i = 1; i <= n; ++i) cout << sub123::oneroot(i) << '\n'; } else { } return 0; }

Compilation message (stderr)

Main.cpp: In function 'void sub4::process()':
Main.cpp:147:17: warning: unused variable 'p' [-Wunused-variable]
  147 |             int p = P[c][0], w = P[c][1];
      |                 ^
#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...