Submission #952153

#	Time	Username	Problem	Language	Result	Execution time	Memory
952153		vjudge1	Museum (CEOI17_museum)	C++14	100 / 100	507 ms	756000 KiB

museum

#include<bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
using namespace std;
const int MAXN = 1e4 + 5;
int f[MAXN][MAXN][2], k, siz[MAXN];
vector<pii> edge[MAXN];
void dfs(int i, int fa){
	siz[i] = 1;
	f[i][0][0] = f[i][1][0] = f[i][0][1] = f[i][1][1] = 0;
	for(pii v : edge[i]){
		if(v.F == fa) continue;
		dfs(v.F, i);
		for(int p = min(k, siz[i]); p >= 1; p--){
			for(int x = 0; x <= min(k, siz[v.F]); x++){
				f[i][p + x][0] = min(f[i][p + x][0], f[i][p][0] + f[v.F][x][0] + 2 * v.S);
				f[i][p + x][1] = min(f[i][p + x][1], f[i][p][0] + f[v.F][x][1] + v.S);
				f[i][p + x][1] = min(f[i][p + x][1], f[i][p][1] + f[v.F][x][0] + 2 * v.S);
			}
		}
		siz[i] += siz[v.F];
	}
}
int main(){
	int n, x, u, v, c;
	scanf("%d%d%d", &n, &k, &x);
	for(int i = 1; i < n; i++){
		scanf("%d%d%d", &u, &v, &c);
		edge[u].push_back(mp(v, c));
		edge[v].push_back(mp(u, c));
	}
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= k; j++)
			f[i][j][1] = f[i][j][0] = 1e9;
	dfs(x, 0);
	printf("%d", f[x][k][1]);
	return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d%d%d", &n, &k, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d%d%d", &u, &v, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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