제출 #708408

#제출 시각아이디문제언어결과실행 시간메모리
708408600Mihnea도로 폐쇄 (APIO21_roads)C++17
0 / 100
2079 ms17608 KiB
#include "roads.h" #include <cmath> #include <functional> #include <fstream> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <cassert> #include <bitset> #include <sstream> #include <chrono> #include <cstring> #include <numeric> using namespace std; typedef long long ll; #define all(x) x.begin(), x.end() #define f first #define s second #define pb push_back #define pii pair<int, int> #define ve vector #define vei vector<int> #define vell vector<ll> #define sz(x) ((int)x.size()) #define each(it, x) for (auto &it : x) #define debug(x) cout << #x << " = " << x << "\n"; #define FU function #define VO void vell minimum_closure_costs(int N, vei U, vei V, vei W) { int n = N; assert(sz(U) == n - 1); assert(sz(V) == n - 1); assert(sz(W) == n - 1); #ifdef ONPC if (0) { debug(n); each(it, U) cout << it << " "; cout << "\n"; each(it, V) cout << it << " "; cout << "\n"; each(it, W) cout << it << " "; cout << "\n"; } #endif ve<ve<pii>> g(n); for (int i = 0; i < n - 1; i++) g[U[i]].pb({ V[i], W[i] }), g[V[i]].pb({ U[i], W[i] }); vei ord, deg(n, 0), pap(n, -1), upp(n, 0); for (int i = 0; i < n; i++) deg[i] = sz(g[i]); vector<bool> vis(n, 0); ord.push_back(0); vis[0] = 1; for (int i = 0; i < (int)ord.size(); i++) { int a = ord[i]; ve<pii> kids; each(it, g[a]) { int b = it.f, c = it.s; if (vis[b]) continue; upp[b] = c; vis[b] = 1; ord.pb(b); kids.pb({ b, c }); } g[a] = kids; } assert((int)ord.size() == n); reverse(all(ord)); vei loc(n); for (int i = 0; i < n; i++) loc[ord[i]] = i; for (int i = 0; i < n; i++) sort(g[i].begin(), g[i].end(), [&](pair<int, int> i, pair<int, int> j) {return deg[i.first] > deg[j.first]; }); vector<vector<int>> devine(n); for (int i = 0; i < n; i++) { devine[deg[i]].pb(i); } vell sol(n, 0); vei verts; vell dp0(n, 0), dp1(n, 0); ll smsz = 0; for (int k = n - 1; k >= 0; k--) { each(x, devine[k]) verts.pb(x); smsz += sz(verts); sort(all(verts), [&](int a, int b) {return loc[a] < loc[b]; }); // 0 => are gradul <= k + 0 // 1 => are gradul <= k + 1 ll print = 0; each(a, verts) { assert(deg[a] >= k); each(rem, vei({ k - 1, k })) { // sterg muchia => dp1 + cost // pastrez muchia => dp0 int total = sz(g[a]); int pastrez = min(total, rem); ll su = 0; each(it, g[a]) if (deg[a] >= k) su += dp1[it.first] + it.second; else break; vector<ll> difs; each(it, g[a]) if (deg[a] >= k) difs.pb(min(0LL, dp0[it.first] - dp1[it.first] - it.second)); else break; sort(difs.begin(), difs.end()); for (int i = 0; i < pastrez; i++) { assert(0 <= i && i < sz(difs)); su += difs[i]; } if (rem == k - 1) dp0[a] = su; else dp1[a] = su; } if (a == 0) { print += dp1[a]; } else { if (deg[pap[a]] < k) { print += min(dp0[a], dp1[a] + upp[a]); } } assert(dp0[a] >= dp1[a]); } sol[k] = print; } assert(smsz <= 3 * n); return sol; }
#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...