Submission #982619

#	Time	Username	Problem	Language	Result	Execution time	Memory
982619		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	2049 ms	25536 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<pair<long long, long long>> g[200001];
vector<long long> v;
long long n, i, j;
long long dp[200001][2];

void dfs(long long x, long long pr, long long k, long long c) {
	for (auto y : g[x]) if (y.first != pr) dfs(y.first, x, k, y.second);
	vector<long long> vv;
	for (auto y : g[x]) {
		if (y.first == pr) continue;
		dp[x][0] += dp[y.first][0];
	}
	dp[x][1] = dp[x][0];
	for (auto y : g[x]) {
		if (y.first == pr) continue;
		vv.push_back({-dp[y.first][0] + dp[y.first][1] + y.second});
	}
	sort(vv.begin(), vv.end());
	//long long w = vv.size() * 52;
	long long w = (long long)vv.size() - k;
	for (long long i = 0; i < min((long long)vv.size(), w + 1); i++) {
		dp[x][0] += vv[i];
	}
	for (long long i = 0; i < min((long long)vv.size(), w); i++) {
		dp[x][1] += vv[i];
	}
	//cout << x << " " << dp[x][0] << " " << dp[x][1] << "\n";
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	for (long long i = 0; i < N - 1; i++) {
		g[U[i]].push_back({V[i], W[i]});
		g[V[i]].push_back({U[i], W[i]});
	}
	for (long long i = 0; i < N; i++) {
		for (long long j = 0; j < N; j++) dp[j][0] = dp[j][1] = 0;
		dfs(0, 0, i, 0);
		v.push_back(dp[0][1]);
	}
  return v;
}

/*
 *
5
0 1 1
0 2 4
0 3 3
2 4 2

 * */

• 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