Submission #148340

#	Time	Username	Problem	Language	Result	Execution time	Memory
148340		luciocf	Museum (CEOI17_museum)	C++14	20 / 100	136 ms	1372 KiB

museum

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e4+10;

int nivel[maxn], dist[maxn], pai[maxn];

bool mark[maxn];

vector<pii> grafo[maxn];

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

		nivel[v] = nivel[u]+1, dist[v] = dist[u]+w;
		pai[v] = u;
		dfs(v, u);
	}
}

int main(void)
{
	int n, k, x;
	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);

	int ans = 1e9+10;

	for (int i = 1; i <= n; i++)
	{
		if (nivel[i] > k) continue;

		memset(mark, 0, sizeof mark);

		priority_queue<pii, vector<pii>, greater<pii>> fila;

		int u = i;
		while (true)
		{
			mark[u] = 1;
			if (u == x) break;
			u = pai[u];
		}

		u = i;
		while (true)
		{
			for (auto v: grafo[u])
				if (!mark[v.first])
					fila.push({v.second, v.first});

			if (u == x) break;
			u = pai[u];
		}

		int aux = 0, temp = 0;
		while (aux < k-nivel[i]-1)
		{
			++aux;

			u = fila.top().second;
			int w = fila.top().first;
			fila.pop();

			mark[u] = 1, temp += w;

			for (auto v: grafo[u])
				if (!mark[v.first])
					fila.push({v.second, v.first});
		}

		ans = min(ans, 2*temp+dist[i]);
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:31: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:36: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: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20