Submission #492808

#	Time	Username	Problem	Language	Result	Execution time	Memory
492808		ntabc05101	Museum (CEOI17_museum)	C++14	80 / 100	499 ms	1048580 KiB

museum

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

#define taskname ""

const long long inf = 1e18;
const int mxN = 10002;

int n, k, x;
vector< pair<int, int> > adj[mxN];
int sz[mxN];
long long dp[mxN][mxN][2];

void dfs(int u, int p = -1) {
	sz[u] = 1;
	for (int i = 2; i <= k; i++) {
		dp[u][i][0] = dp[u][i][1] = inf;
	}
	for (auto &to: adj[u]) {
		if (to.first != p) {
			dfs(to.first, u);
			for (int i = min(sz[u] + sz[to.first], k); i > 1; i--) {
				for (int j = min(sz[to.first] , i - 1); j >= max(1, i - sz[u]); j--) {
					dp[u][i][1] = min({dp[u][i][1], dp[u][i - j][1] + dp[to.first][j][0] + (to.second << 1), dp[u][i - j][0] + dp[to.first][j][1] + to.second});
					dp[u][i][0] = min({dp[u][i][0], dp[u][i - j][0] + dp[to.first][j][0] + (to.second << 1)});
				}
			}
			sz[u] += sz[to.first];
		}
	}
}

int main() {
	if (fopen(taskname".inp", "r")) {
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
	else {
		if (fopen(taskname".in", "r")) {
			freopen(taskname".in", "r", stdin);
			freopen(taskname".out", "w", stdout);
		}
	}

	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> k >> x; x--;
	for (int i = 0, x, y, w; i < n - 1; i++) {
		cin >> x >> y >> w; x--; y--;
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}

	dfs(x);

	cout << dp[x][k][1] << "\n";

	return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:35:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:36:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:40:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |    freopen(taskname".in", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:41:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |    freopen(taskname".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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