oj.uz

Submission #151051

# Submission time Handle Problem Language Result Execution time Memory
151051 2019-09-01T16:04:15 Z luciocf Museum (CEOI17_museum) C++14
80 / 100
 1370 ms 1048576 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)
{
	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]);

}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 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 51520 KB Output is correct
2 Correct 184 ms 51788 KB Output is correct
3 Correct 548 ms 198984 KB Output is correct
4 Correct 290 ms 89464 KB Output is correct
5 Correct 208 ms 57080 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 51520 KB Output is correct
2 Correct 184 ms 51788 KB Output is correct
3 Correct 548 ms 198984 KB Output is correct
4 Correct 290 ms 89464 KB Output is correct
5 Correct 208 ms 57080 KB Output is correct
6 Correct 190 ms 51024 KB Output is correct
7 Correct 391 ms 128400 KB Output is correct
8 Correct 501 ms 50716 KB Output is correct
9 Correct 389 ms 50668 KB Output is correct
10 Correct 211 ms 51208 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 184 ms 51520 KB Output is correct
7 Correct 184 ms 51788 KB Output is correct
8 Correct 548 ms 198984 KB Output is correct
9 Correct 290 ms 89464 KB Output is correct
10 Correct 208 ms 57080 KB Output is correct
11 Correct 190 ms 51024 KB Output is correct
12 Correct 391 ms 128400 KB Output is correct
13 Correct 501 ms 50716 KB Output is correct
14 Correct 389 ms 50668 KB Output is correct
15 Correct 211 ms 51208 KB Output is correct
16 Correct 277 ms 122656 KB Output is correct
17 Correct 668 ms 435576 KB Output is correct
18 Correct 407 ms 176560 KB Output is correct
19 Correct 512 ms 120904 KB Output is correct
20 Correct 284 ms 121520 KB Output is correct
21 Correct 1311 ms 915052 KB Output is correct
22 Correct 1111 ms 748676 KB Output is correct
23 Correct 1295 ms 746284 KB Output is correct
24 Correct 1071 ms 747476 KB Output is correct
25 Runtime error 1370 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)