Submission #935533

#	Time	Username	Problem	Language	Result	Execution time	Memory
935533		MinaRagy06	Road Closures (APIO21_roads)	C++17	24 / 100	2096 ms	29812 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];
priority_queue<ll, vector<ll>, greater<ll>> pending[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();
	}
	build(0, -1);
	par[0] = {0, (int)1e18};
	vector<ll> ret(n);
	for (int m = 0; m < n; m++) {
		for (auto i : order) {
			dp[i][1] = 0;
			dp[i][0] = par[i][1];
			vector<ll> vals;
			for (auto [nxt, w] : adj[i]) {
				dp[i][1] += dp[nxt][1];
				dp[i][0] += dp[nxt][1];
				vals.push_back(dp[nxt][0] - dp[nxt][1]);
			}
			sort(vals.begin(), vals.end());
			int cnt = max(0, deg[i] - m - 1);
			for (int j = 0; j < cnt; j++) {
				dp[i][0] += vals[j];
			}
			cnt = max(0, deg[i] - m);
			if (i != 0 && cnt == deg[i]) {
				dp[i][1] = 1e18;
			} else {
				for (int j = 0; j < cnt; j++) {
					dp[i][1] += vals[j];
				}
			}
			dp[i][1] = min(dp[i][1], dp[i][0]);
		}
		ret[m] = dp[0][1];
	}
	return ret;
}

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