Submission #980728

#	Time	Username	Problem	Language	Result	Execution time	Memory
980728		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	23 ms	5208 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"

using namespace std;
using ll = long long;

const int N = 2020;
const ll INF = 1e18;

vector<pair<int, ll>> g[N];

int n;
ll dp[N][N][2];

void dfs(int s, int p) {
	vector<pair<int, ll>> child;
	for (auto [to, x] : g[s]) if (to != p) {
		dfs(to, s);
		child.push_back({to, x});
	}
	int m = (int)child.size();

	// cout << "vertex: " << s << '\n';
	for (auto [t, w] : child) {
		// cout << "(" << t << " " << w << ") ";
		dp[s][0][0] += dp[t][0][0] + w;
	}

	// cout << '\n';
	for (int k = 1; k < n; k++) {
		vector<ll> values;
		for (auto [t, w] : child) {
			dp[s][k][0] += dp[t][k][0] + w;
			dp[s][k][1] += dp[t][k][0] + w;
			values.push_back(dp[t][k][1] - dp[t][k][0] - w);
		}
		sort(values.begin(), values.end());
		int l = 0;
		while (l < min((int)values.size(), k) && values[l] <= 0)
			dp[s][k][0] += values[l++];
		l = 0;
		while (l < min((int)values.size(), k - 1) && values[l] <= 0)
			dp[s][k][1] += values[l++];
	}
	// for (int k = 0; k < n; k++)
	// 	cout << dp[s][k] << ' ';
	// cout << '\n';	
}

vector<ll> minimum_closure_costs(int N, vector<int> U,
                                             vector<int> V,
                                             vector<int> W) {
	bool is1st = true;
	bool is2nd = true;

	n = N;
	for (int i = 0; i < n - 1; i++) {
		is1st &= (U[i] == 0);
		is2nd &= (U[i] == i);
		is2nd &= (V[i] == i + 1);
		g[U[i]].push_back({V[i], W[i]});
		g[V[i]].push_back({U[i], W[i]});
	}

	if (is1st) {
		vector<ll> res(n);
		sort(W.begin(), W.end());
		ll s = 0;
		for (int i = 0; i < n - 1; i++) {
			s += W[i];
			res[n - 2 - i] = s; 
		}
		return res;
	}

	if (is2nd) {
		vector<ll> res(n);
		int dp[n][2] = {};
		for (int i = 1; i < n; i++) {
			dp[i][0] = dp[i - 1][1];
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + W[i - 1];
		}
		
		res[1] = min(dp[n - 1][0], dp[n - 1][1]);
		ll s = 0;
		for (ll c : W) s += c;
		res[0] = s;
		return res;
	}

	dfs(0, -1);

	vector<ll> res;
	for (int i = 0; i < n; i++)
		res.push_back(dp[0][i][0]);

	return res;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:21:6: warning: unused variable 'm' [-Wunused-variable]
   21 |  int m = (int)child.size();
      |      ^

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