oj.uz

Submission #151053

# Submission time Handle Problem Language Result Execution time Memory
151053 2019-09-01T16:07:13 Z luciocf Museum (CEOI17_museum) C++14
100 / 100
 974 ms 746080 KB 
#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)
{
	for (int i = 2; i <= k; i++)
		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 = dp[u][i-j][0] + 2*w + dp[v][j][1];
				int c2 = dp[u][i-j][1] + w + dp[v][j][0];

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

				dp[u][i][1] = min(dp[u][i][1], dp[u][i-j][1] + 2*w + dp[v][j][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]);

}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:64: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:69: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 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 51332 KB Output is correct
2 Correct 184 ms 51668 KB Output is correct
3 Correct 473 ms 181468 KB Output is correct
4 Correct 274 ms 90948 KB Output is correct
5 Correct 201 ms 59128 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 51332 KB Output is correct
2 Correct 184 ms 51668 KB Output is correct
3 Correct 473 ms 181468 KB Output is correct
4 Correct 274 ms 90948 KB Output is correct
5 Correct 201 ms 59128 KB Output is correct
6 Correct 183 ms 50808 KB Output is correct
7 Correct 352 ms 125900 KB Output is correct
8 Correct 464 ms 50356 KB Output is correct
9 Correct 365 ms 50408 KB Output is correct
10 Correct 206 ms 51120 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 184 ms 51332 KB Output is correct
7 Correct 184 ms 51668 KB Output is correct
8 Correct 473 ms 181468 KB Output is correct
9 Correct 274 ms 90948 KB Output is correct
10 Correct 201 ms 59128 KB Output is correct
11 Correct 183 ms 50808 KB Output is correct
12 Correct 352 ms 125900 KB Output is correct
13 Correct 464 ms 50356 KB Output is correct
14 Correct 365 ms 50408 KB Output is correct
15 Correct 206 ms 51120 KB Output is correct
16 Correct 246 ms 121880 KB Output is correct
17 Correct 515 ms 433520 KB Output is correct
18 Correct 347 ms 158772 KB Output is correct
19 Correct 447 ms 120628 KB Output is correct
20 Correct 256 ms 121208 KB Output is correct
21 Correct 848 ms 745748 KB Output is correct
22 Correct 771 ms 745552 KB Output is correct
23 Correct 974 ms 745560 KB Output is correct
24 Correct 805 ms 745484 KB Output is correct
25 Correct 906 ms 746080 KB Output is correct