oj.uz

Submission #151050

# Submission time Handle Problem Language Result Execution time Memory
151050 2019-09-01T15:50:03 Z luciocf Museum (CEOI17_museum) C++14
80 / 100
 1037 ms 1048580 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], f[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++)
		f[u][i][0] = f[u][i][1] = 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[u][i-j][0] + 2*w + dp[v][j][1];
				int c2 = f[u][i-j][1] + w + dp[v][j][0];

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

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

	for (int i = 1; i <= k; i++)
	{
		dp[u][i][0] = f[u][i][0];
		dp[u][i][1] = f[u][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]);

}

Compilation message

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 100728 KB Output is correct
2 Correct 225 ms 101020 KB Output is correct
3 Correct 548 ms 230956 KB Output is correct
4 Correct 325 ms 140144 KB Output is correct
5 Correct 244 ms 108560 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 100728 KB Output is correct
2 Correct 225 ms 101020 KB Output is correct
3 Correct 548 ms 230956 KB Output is correct
4 Correct 325 ms 140144 KB Output is correct
5 Correct 244 ms 108560 KB Output is correct
6 Correct 223 ms 100316 KB Output is correct
7 Correct 415 ms 175552 KB Output is correct
8 Correct 499 ms 99940 KB Output is correct
9 Correct 399 ms 99932 KB Output is correct
10 Correct 244 ms 100500 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 220 ms 100728 KB Output is correct
7 Correct 225 ms 101020 KB Output is correct
8 Correct 548 ms 230956 KB Output is correct
9 Correct 325 ms 140144 KB Output is correct
10 Correct 244 ms 108560 KB Output is correct
11 Correct 223 ms 100316 KB Output is correct
12 Correct 415 ms 175552 KB Output is correct
13 Correct 499 ms 99940 KB Output is correct
14 Correct 399 ms 99932 KB Output is correct
15 Correct 244 ms 100500 KB Output is correct
16 Correct 359 ms 241800 KB Output is correct
17 Correct 972 ms 865820 KB Output is correct
18 Correct 478 ms 278696 KB Output is correct
19 Correct 565 ms 240436 KB Output is correct
20 Correct 377 ms 241004 KB Output is correct
21 Runtime error 1037 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -