Submission #241844

#	Time	Username	Problem	Language	Result	Execution time	Memory
241844		ChrisT	Museum (CEOI17_museum)	C++17	100 / 100	624 ms	784760 KiB

museum

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define mp make_pair
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e4+5, MOD = 1e9+7, BASE = 31, MASK = (1 << 10) - 1;
int dp[MN][MN][2],sz[MN], k, x;
vector<pii> adj[MN]; ll iters;
void dfs (int cur, int par = -1) {
	memset(dp[cur],0x3f,sizeof dp[cur]); dp[cur][1][0] = dp[cur][1][1] = 0;
	for (pii p : adj[cur]) if (p.first != par) dfs(p.first,cur);
	++sz[cur];
	if (adj[cur].size() == 1 && cur != x) return;
	sort (all(adj[cur]),[&](pii a, pii b){return sz[a.first] > sz[b.first];});
	sz[cur] += sz[adj[cur][0].first];
	for (int i = 2; i <= sz[cur]; i++) dp[cur][i][0] = dp[adj[cur][0].first][i-1][0] + adj[cur][0].second * 2, dp[cur][i][1] = dp[adj[cur][0].first][i-1][1] + adj[cur][0].second;
	for (pii p : adj[cur]) if (p != adj[cur][0] && p.first != par) {
		sz[cur] += sz[p.first]; int sofar = min(sz[cur],k);
		for (int i = sofar; i >= 2; i--) {
			int ed = min(sz[p.first],i-1);
			for (int take = 1; take <= ed; take++) {
				dp[cur][i][0] = min(dp[cur][i][0],dp[cur][i-take][0] + dp[p.first][take][0] + p.second * 2);
				dp[cur][i][1] = min(dp[cur][i][1],dp[cur][i-take][1] + dp[p.first][take][0] + p.second * 2);
				dp[cur][i][1] = min(dp[cur][i][1],dp[cur][i-take][0] + dp[p.first][take][1] + p.second);
			}
		}
	}
}
int main () {
	int n;
	scanf ("%d %d %d",&n,&k,&x);
	for (int i = 1; i < n; i++) {
		int a,b,c;
		scanf ("%d %d %d",&a,&b,&c);
		adj[a].emplace_back(b,c); adj[b].emplace_back(a,c);
	}
	dfs(x);
	printf ("%d\n",dp[x][k][1]);
	return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d %d",&n,&k,&x);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
museum.cpp:43:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d",&a,&b,&c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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