제출 #151051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151051		luciocf	Museum (CEOI17_museum)	C++14	80 / 100	1370 ms	1048576 KiB

museum

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e4+10;
const int inf = 1e8+10;

int n, k, x;
int sz[maxn];

int dp[maxn][maxn][2];

vector<pii> grafo[maxn];

void dfs(int u, int p)
{
	sz[u] = 1;

	for (auto pp: grafo[u])
	{
		int v = pp.first;
		if (v == p) continue;

		dfs(v, u);
		sz[u] += sz[v];
	}
}

void solve(int u, int p)
{
	int f[maxn][2];

	for (int i = 2; i <= k; i++)
	{
		f[i][0] = f[i][1] = inf;
		dp[u][i][0] = dp[u][i][1] = inf;
	}

	int soma_sz = 1;

	for (auto pp: grafo[u])
	{
		int v = pp.first, w = pp.second;
		if (v == p) continue;

		solve(v, u);

		soma_sz += sz[v];

		for (int i = soma_sz; i >= 2; i--)
		{
			for (int j = max(0, i-soma_sz+sz[v]); j <= min(i, sz[v]); j++)
			{
				int c1 = f[i-j][0] + 2*w + dp[v][j][1];
				int c2 = f[i-j][1] + w + dp[v][j][0];

				f[i][0] = min({f[i][0], c1, c2});

				f[i][1] = min(f[i][1], f[i-j][1] + 2*w + dp[v][j][1]);
			}
		}
	}

	for (int i = 1; i <= k; i++)
	{
		dp[u][i][0] = f[i][0];
		dp[u][i][1] = f[i][1];
	}
}

int main(void)
{
	scanf("%d %d %d", &n, &k, &x);

	for (int i = 1; i < n; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		grafo[u].push_back({v, w});
		grafo[v].push_back({u, w});
	}

	dfs(x, 0);
	solve(x, 0);

	printf("%d\n", dp[x][k][0]);

}

컴파일 시 표준 에러 (stderr) 메시지

museum.cpp: In function 'int main()':
museum.cpp:75:7: 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:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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