Submission #1088953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088953		SamNguyen	Museum (CEOI17_museum)	C++14	100 / 100	550 ms	784720 KiB

museum

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

#define INPFILE ".inp"
#define OUTFILE ".out"

const int INF = 3e8 + 7;

template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
	if (x > y) { x = y; return true; }
	return false;
}

template <class T>
inline void minimise_pair(pair<T, T> &x, T y) {
	if (x.second > y)
		swap(x.second, y);
	if (x.first > x.second)
		swap(x.second, x.first);
}

const int MAX = 1e4 + 3;
int N, K, ROOT;
vector<pair<int, int>> adj[MAX];

void input() {
	cin >> N >> K >> ROOT;
	for (int t = N - 1; t--; ) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
}

int dp[2][MAX][MAX], sz[MAX];

void dfs(int u, int p) {
	sz[u] = 1;
	for (const auto &e : adj[u]) {
		int v, w;
		tie(v, w) = e;
		if (v == p) continue;
		dfs(v, u);
		sz[u] += sz[v];
	}

	static int g[MAX][2];

	g[0][true ] = 0;
	g[0][false] = 0;
	for (int s = min(K, sz[u]); s >= 1; s--) 
		g[s][true ] = g[s][false] = INF;

	int cum_size = 1;

	for (const auto &e : adj[u]) {
		int v, w;
		tie(v, w) = e;
		if (v == p) continue;

		for (int s = min(K, cum_size + sz[v]); s >= 1; s--) {
			for (int y = min(s, sz[v] + 1); y >= 1; y--) {
				int x = s - y;
				minimise(g[s][true ], g[x][true ] + 2 * w + dp[true ][v][y - 1]);
				minimise(g[s][false], g[x][false] + 2 * w + dp[true ][v][y - 1]);
				minimise(g[s][false], g[x][true ] +     w + dp[false][v][y - 1]);

				if (x > cum_size)
					break;
			}
		}
		cum_size += sz[v];

	}

	dp[true ][u][0] = 0;
	dp[false][u][0] = 0;
	for (int k = 1; k <= min(K, sz[u]); k++) {
		minimise(dp[false][u][k], g[k][false]);
		minimise(dp[true ][u][k], g[k][true ]);
	}
}

void solve() {
	if (K == 1) {
		cout << 0;
		return;
	}

	for (int t : {0, 1})
	for (int u = 0; u <= N; u++)
	for (int k = 0; k <= K; k++)
		dp[t][u][k] = INF;
	
	adj[0].emplace_back(ROOT, 0);
	dfs(0, -1);

	int ans = dp[false][0][K];
	cout << ans;
}
	
int main(void) {
	if (fopen(INPFILE, "r")) {
		freopen(INPFILE, "r", stdin);
		freopen(OUTFILE, "w", stdout);
	}
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();

	return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:105:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   freopen(INPFILE, "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
museum.cpp:106:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   freopen(OUTFILE, "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20