제출 #935801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
935801		MinaRagy06	도로 폐쇄 (APIO21_roads)	C++17	100 / 100	164 ms	36236 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);
				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);
				}
			}
			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);
			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});
				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]);
			}
			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();
					taken[i].push(x);
					sum[i] += x;
					torem.push_back(x);
				}
				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];
					dp[i][1] = min(dp[i][1], s + sum[i]);
				}
				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();
			}
			dp[i][1] = min(dp[i][1], dp[i][0]);
			if (par[i][0] == i) {
				ret[m] += dp[i][1];
			}
		}
		order = neworder;
	}
	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