Submission #935799

#	Time	Username	Problem	Language	Result	Execution time	Memory
935799		MinaRagy06	Road Closures (APIO21_roads)	C++17	100 / 100	170 ms	38488 KiB

roads

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "roads.h"
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

const int N = 100'005;
vector<array<int, 2>> adj[N];
ll dp[N][2];
int deg[N];
vector<int> order;
array<ll, 2> par[N];
void build(int i, int p) {
	vector<array<int, 2>> newadj;
	for (auto [nxt, w] : adj[i]) {
		if (nxt == p) continue;
		build(nxt, i);
		par[nxt] = {i, w};
		newadj.push_back({nxt, w});
	}
	adj[i] = newadj;
	order.push_back(i);
}
priority_queue<ll> taken[N];
ll sum[N];
priority_queue<ll, vector<ll>, greater<ll>> pending[N];
vector<int> rem[N];
bool in[N];
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {
	for (int i = 0; i < n - 1; i++) {
		adj[U[i]].push_back({V[i], W[i]});
		adj[V[i]].push_back({U[i], W[i]});
	}
	for (int i = 0; i < n; i++) {
		deg[i] = adj[i].size();
		rem[deg[i]].push_back(i);
		in[i] = 1;
	}
	build(0, -1);
	par[0] = {0, (int)1e18};
	vector<ll> ret(n, 0);
	for (int m = 0; m < n; m++) {
		for (auto i : rem[m]) {
			in[i] = 0;
			if (par[i][0] != i) {
				int p = par[i][0], w = par[i][1];
				pending[p].push(w);
// 				cout << "+ " << p << ' ' << w << '\n';
				while (taken[p].size() && pending[p].top() < taken[p].top()) {
					ll x = taken[p].top();
					ll y = pending[p].top();
					taken[p].pop();
					sum[p] -= x;
					pending[p].pop();
					taken[p].push(y);
					sum[p] += y;
					pending[p].push(x);
// 					cout << "- " << p << ' ' << y << '\n';
// 					cout << "+ " << p << ' ' << x << '\n';
				}
			}
			for (auto [nxt, w] : adj[i]) {
				par[nxt][0] = nxt;
			}
		}
		vector<int> neworder;
		for (auto i : order) {
			if (!in[i]) continue;
			neworder.push_back(i);
// 			dp[i][1] = 0;
// 			dp[i][0] = par[i][1];
			vector<ll> vals;
			vector<array<int, 2>> newadj;
			ll ttl = 0;
			for (auto [nxt, w] : adj[i]) {
				if (!in[nxt]) continue;
				newadj.push_back({nxt, w});
// 				if (i == 0) {
// 					cout << ">>> " << nxt << ' ' << dp[nxt][1] << '\n';
// 				}
				ttl += dp[nxt][1];
				vals.push_back(dp[nxt][0] - dp[nxt][1]);
			}
			adj[i] = newadj;
			sort(vals.begin(), vals.end());
			int cnt = max(0, deg[i] - m - 1);
			int sz = max(0, cnt - SZ(vals));
			while (SZ(taken[i]) > sz) {
				ll x = taken[i].top();
				taken[i].pop();
				sum[i] -= x;
				pending[i].push(x);
			}
			while (SZ(taken[i]) < sz && SZ(pending[i])) {
				ll x = pending[i].top();
				pending[i].pop();
				taken[i].push(x);
				sum[i] += x;
			}
			ll s = par[i][1] + ttl;
			for (int j = 0; j < cnt - SZ(taken[i]); j++) {
				s += vals[j];
			}
			dp[i][0] = s + sum[i];
			vector<ll> torem;
			for (int j = cnt - SZ(taken[i]) - 1; j >= 0; j--) {
				if (pending[i].empty()) break;
				torem.push_back(pending[i].top());
				pending[i].pop();
				taken[i].push(torem.back());
				sum[i] += torem.back();
				s -= vals[j];
				dp[i][0] = min(dp[i][0], s + sum[i]);
			}
// 			if (m == 1 && i == 1) {
// 				cout << SZ(pending[i]) << endl;
// 			}
			while (SZ(torem)) {
				ll x = torem.back();
				torem.pop_back();
				assert(x == taken[i].top());
				taken[i].pop();
				sum[i] -= x;
				pending[i].push(x);
			}
			torem.clear();

			cnt = max(0, deg[i] - m);
			if (i != 0 && cnt == deg[i]) {
				dp[i][1] = 1e18;
			} else {
				sz = max(0, cnt - SZ(vals));
				while (SZ(taken[i]) < sz && SZ(pending[i])) {
					ll x = pending[i].top();
					pending[i].pop();
// 					if (i == 0) {
// 						cout << ">> " << pending[i].top() << '\n';
// 					}
					taken[i].push(x);
					sum[i] += x;
					torem.push_back(x);
				}
// 				if (m == 1 && i == 0) {
// 					cout << deg[i] << ' ' << SZ(vals) << ' ' << SZ(pending[i]) << ' ' << SZ(taken[i]) << endl;
// 				}
				s = ttl;
				for (int j = 0; j < cnt - SZ(taken[i]); j++) {
					s += vals[j];
				}
				dp[i][1] = s + sum[i];
				for (int j = cnt - SZ(taken[i]) - 1; j >= 0; j--) {
					if (pending[i].empty()) break;
					torem.push_back(pending[i].top());
					pending[i].pop();
					taken[i].push(torem.back());
					sum[i] += torem.back();
					s -= vals[j];
// 					if (i == 0) {
// 						cout << "- " << vals[j] << '\n';
// 						cout << "+ " << torem.back() << '\n';
// 					}
					dp[i][1] = min(dp[i][1], s + sum[i]);
				}
// 				if (i == 0) {
// 					cout << "> " << ttl << ' ' << sum[i] << ' ' << min(cnt, SZ(vals)) << ' ' << sz << '\n';
// 					cout << dp[i][1] << '\n';
// 				}
				while (SZ(torem)) {
					ll x = torem.back();
					torem.pop_back();
					assert(x == taken[i].top());
					taken[i].pop();
					sum[i] -= x;
					pending[i].push(x);
				}
				torem.clear();
// 				for (int j = 0; j < cnt; j++) {
// 					dp[i][1] += vals[j];
// 				}
			}
			dp[i][1] = min(dp[i][1], dp[i][0]);
// 			cout << i << ": " << dp[i][0] << ' ' << dp[i][1] << '\n';
			if (par[i][0] == i) {
				ret[m] += dp[i][1];
			}
		}
		order = neworder;
// 		for (auto i : order) {
// 			cout << i << ' ';
// 		}
// 		cout << "\n\n";
// 		ret[m] = dp[0][1];
	}
	return ret;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22