Submission #873493

#TimeUsernameProblemLanguageResultExecution timeMemory
873493sleepntsheepPaths (RMI21_paths)C++17
48 / 100
790 ms17956 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() #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,tune=native") 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[2004], tout[2004], P[2004][2], rv[2004],del[2004], timer; ll rt[N]{0}; struct segtree { pair<ll, int> t[4005]; ll lz[4005]{0}; segtree() { } void build(int v, int l, int r) { lz[v]=0; if (l >= r) { int u = rv[l]; if (tin[u]==tout[u]) t[v] = {rt[u], u}; else t[v] = {-0,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; 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) { del[u]=0; rv[tin[u] = timer++] = u; for (auto [w, v] : g[u]) if (v-p) rt[v]=rt[P[v][0]=u]+(P[v][1]=w),dfs1(v, u); tout[u] = timer - 1; } ll ans; void process() { auto x = t.qry(0,n-1,0,0,n-1); if (x.first <= 0) return; ans += x.first; for (int c = x.second; P[c][0]; c = P[c][0]) if(!del[c]) t.upd(tin[c], tout[c], -P[c][1], 0, 0, n-1), del[c]=1; } ll oneroot(int root) { P[root][0]=P[root][1]=rt[root]=ans=timer=0; dfs1(root,root); assert(timer==n); t.build(0,0,n-1); for (int 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; }
#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...