Submission #980478

#	Time	Username	Problem	Language	Result	Execution time	Memory
980478		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	151 ms	5212 KiB

roads

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

using namespace std;
using ll = long long;

const int N = 2020;

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

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

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] += dp[t][0] + w;
	}
	// cout << '\n';
	for (int k = 1; k < n; k++) {
		vector<ll> values;
		for (auto [t, w] : child) {
			dp[s][k] += dp[t][k] + w;
			values.push_back(dp[t][k - 1] - dp[t][k] - w);
		}
		sort(values.begin(), values.end());
		int l = 0;
		while (l < min((int)values.size(), k) && values[l] <= 0)
			dp[s][k] += 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) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		g[U[i]].push_back({V[i], W[i]});
		g[V[i]].push_back({U[i], W[i]});
	}

	dfs(0, -1);

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

	return res;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:20:6: warning: unused variable 'm' [-Wunused-variable]
   20 |  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