Submission #960720

#TimeUsernameProblemLanguageResultExecution timeMemory
960720peterandvoiRoad Closures (APIO21_roads)C++17
0 / 100
212 ms119336 KiB
#include "roads.h" #include <bits/stdc++.h> using namespace std; #ifdef ngu #include "debug.h" #else #define debug(...) 42 #endif const long long mxN = (long long) 1e5 + 5; const long long LOG = 30; const long long NODE = mxN * LOG; const long long INF = (long long) 1e18; #define BIT(x, i) ((x) >> (i) & 1) long long N, K; long long node; long long dp[mxN][2]; long long deg[mxN]; bool vis[mxN], on[mxN]; long long nxt[NODE][2], cnt[NODE]; long long sum[NODE]; vector<long long> pos[mxN]; vector<pair<long long, long long>> g[mxN], graph[mxN]; void ins(long long u, long long x) { long long p = u; for (long long i = LOG - 1; i >= 0; --i) { long long c = BIT(x, i); if (!nxt[p][c]) { nxt[p][c] = ++node; } p = nxt[p][c]; sum[p] += x; cnt[p]++; } } void ers(long long u, long long x) { long long p = u; for (long long i = LOG - 1; i >= 0; --i) { long long c = BIT(x, i); p = nxt[p][c]; sum[p] -= x; cnt[p]--; } } long long get(long long u, long long k) { if (!k) { return 0; } long long res = 0; long long p = u; for (long long i = LOG - 1; i >= 0; --i) { if (cnt[nxt[p][0]] >= k) { p = nxt[p][0]; } else { k -= cnt[nxt[p][0]]; res += sum[nxt[p][0]]; p = nxt[p][1]; } } return res + k * (sum[p] / cnt[p]); } long long rt; void dfs(long long u) { dp[u][0] = dp[u][1] = INF; vis[u] = true; long long s = 0; vector<long long> delta; for (auto [v, w] : graph[u]) { if (!vis[v]) { dfs(v); delta.emplace_back(dp[v][1] - dp[v][0] + w); s += dp[v][0]; } } sort(delta.begin(), delta.end()); for (long long i = 1; i < (long long) delta.size(); ++i) { delta[i] += delta[i - 1]; } long long need = deg[u] - K; long long m = (long long) delta.size(), tm = deg[u] - m - (u != rt); for (long long i = 0; i <= min(m, need); ++i) { if (i <= need - 1 && need - 1 - i <= tm) { dp[u][1] = min(dp[u][1], s + (i ? delta[i - 1] : 0LL) + get(u, need - 1 - i)); } if (need - i <= tm) { dp[u][0] = min(dp[u][0], s + (i ? delta[i - 1] : 0LL) + get(u, need - i)); } } } vector<long long> ver; void turn_on(long long u) { on[u] = true; ver.emplace_back(u); for (auto [v, w] : g[u]) { if (on[v]) { ers(v, w); graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); } else { ins(u, w); } } } std::vector<long long> minimum_closure_costs(int n, std::vector<int> U, std::vector<int> V, std::vector<int> W) { N = n; node = N; vector<long long> res(N); for (long long i = 0; i < N; ++i) { U[i]++; V[i]++; deg[U[i]]++; deg[V[i]]++; g[U[i]].emplace_back(V[i], W[i]); g[V[i]].emplace_back(U[i], W[i]); } for (long long i = 1; i <= N; ++i) { pos[deg[i]].emplace_back(i); } for (long long i = N - 1; i >= 0; --i) { K = i; for (long long u : pos[i + 1]) { turn_on(u); } for (long long u : ver) { if (!vis[u]) { rt = u; dfs(u); res[i] += dp[u][0]; } } for (long long u : ver) { vis[u] = false; } } return res; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...