Submission #725776

#	Time	Username	Problem	Language	Result	Execution time	Memory
725776		SanguineChameleon	Road Closures (APIO21_roads)	C++17	31 / 100	2088 ms	44492 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
set<pair<int, int>> adj[maxN];
vector<pair<int, int>> pre_adj[maxN];
vector<int> bucket[maxN];
int deg[maxN];
bool is_bad[maxN];
bool flag[maxN];
long long dp[maxN][2];
int K;

void dfs(int u, int par) {
	flag[u] = true;
	dp[u][0] = inf;
	dp[u][1] = inf;
	long long sum = 0;
	vector<long long> cost;
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (v == par) {
			continue;
		}
		dfs(v, u);
		sum += dp[v][1];
		cost.push_back(dp[v][0] + w - dp[v][1]);
	}
	sort(cost.begin(), cost.end());
	int cnt = cost.size();
	for (int i = 0; i < 2; i++) {
		if (cnt + i <= K) {
			dp[u][i] = min(dp[u][i], sum);
		}
	}
	for (auto w: cost) {
		sum += w;
		cnt--;
		for (int i = 0; i < 2; i++) {
			if (cnt + i <= K) {
				dp[u][i] = min(dp[u][i], sum);
			}
		}
	}
}

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++) {
		pre_adj[U[i]].push_back({V[i], W[i]});
		pre_adj[V[i]].push_back({U[i], W[i]});
		deg[U[i]]++;
		deg[V[i]]++;
	}
	for (int i = 0; i < N; i++) {
		bucket[deg[i]].push_back(i);
	}
	vector<long long> res(N);
	vector<int> bad;
	for (K = N - 1; K >= 0; K--) {
		//cout << "calc" << " " << K << '\n';
		for (auto u: bad) {
			flag[u] = false;
		}
		for (auto u: bad) {
			if (!flag[u]) {
				dfs(u, -1);
				res[K] += dp[u][0];
			}
		}
		for (auto u: bucket[K]) {
			//cout << "add" << " " << u << '\n';
			for (auto e: pre_adj[u]) {
				int v = e.first;
				int w = e.second;
				adj[u].insert({v, w});
				adj[v].insert({u, w});
			}
			bad.push_back(u);
			is_bad[u] = true;
		}
	}
	return res;
}

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