Submission #725775

#	Time	Username	Problem	Language	Result	Execution time	Memory
725775		SanguineChameleon	Road Closures (APIO21_roads)	C++17	24 / 100	2065 ms	22548 KiB

roads

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

const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
vector<pair<int, int>> adj[maxN];
long long dp[maxN][2];
int K;

void dfs(int u, int par) {
	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 deg = cost.size();
	for (int i = 0; i < 2; i++) {
		if (deg + i <= K) {
			dp[u][i] = min(dp[u][i], sum);
		}
	}
	for (auto w: cost) {
		sum += w;
		deg--;
		for (int i = 0; i < 2; i++) {
			if (deg + 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++) {
		adj[U[i]].push_back({V[i], W[i]});
		adj[V[i]].push_back({U[i], W[i]});
	}
	vector<long long> res(N);
	for (K = 0; K <= N - 1; K++) {
		dfs(0, -1);
		res[K] = dp[0][0];
	}
	return res;
}

• 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