oj.uz

Submission #148341

# Submission time Handle Problem Language Result Execution time Memory
148341 2019-09-01T03:04:25 Z luciocf Museum (CEOI17_museum) C++14
20 / 100
 136 ms 1128 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 1128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 1128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Incorrect 136 ms 1128 KB Output isn't correct
7 Halted 0 ms 0 KB -