제출 #564539

#제출 시각아이디문제언어결과실행 시간메모리
564539hollwo_pelw도로 폐쇄 (APIO21_roads)C++17
5 / 100
143 ms28520 KiB
#include "roads.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; multiset<int> st[MAXN]; long long sum[MAXN], dp[MAXN][2]; int deg[MAXN], vis[MAXN]; vector<pair<int, int>> adj[MAXN]; inline void upd(int u, int v, int op) { sum[u] += op * v; if (op == +1) st[u].insert(v); if (op == -1) st[u].erase(st[u].find(v)); } void solve(int u) { vector<int> add, del; long long tot = 0; // need to del int X = vis[u], lim = deg[u] - X; while ((int)st[u].size() > lim) upd(u, *st[u].rbegin(), -1); for (auto [v, w] : adj[u]) { if (deg[v] <= X) break; if (vis[v] == X) continue; vis[v] = X; solve(v); tot += dp[v][0]; add.push_back(dp[v][1] + w - dp[v][0]), upd(u, dp[v][1] + w - dp[v][0], +1); } for (int i = 0; i < 2; i++) { while ((int)st[u].size() > lim - i) del.push_back(*st[u].rbegin()), upd(u, *st[u].rbegin(), -1); dp[u][i] = tot + sum[u]; } } vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) { for (int i = 0; i < N - 1; i++) { deg[U[i]] ++, deg[V[i]] ++; adj[U[i]].emplace_back(V[i], W[i]); adj[V[i]].emplace_back(U[i], W[i]); } for (int i = 0; i < N; i++) sort(adj[i].begin(), adj[i].end(), [&](const pair<int, int> &x, const pair<int, int> &y){ return deg[x.first] > deg[y.first]; }); vector<long long> res(N); res[0] = accumulate(W.begin(), W.end(), 0ll); vector<int> p(N); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&](const int &i, const int &j){ return deg[i] < deg[j]; }); for (int X = 1, i = 0; X < N; X++) { for (; i < N && deg[p[i]] == X; i++) { for (auto [v, w] : adj[p[i]]) { if (deg[v] <= X) break; upd(v, w, 1); } } long long ans = 0; for (int j = i; j < N; j++) if (vis[p[j]] != X) { vis[p[j]] = X; solve(p[j]); ans += dp[p[j]][0]; } res[X] = ans; } 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...