oj.uz

Submission #98140

# Submission time Handle Problem Language Result Execution time Memory
98140 2019-02-21T01:49:20 Z luciocf Chase (CEOI17_chase) C++14
70 / 100
 506 ms 183364 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxv = 110;

typedef long long ll;

int n, c;
int num[maxn];

ll soma[maxn], dp[maxn][maxv][2];

vector<int> grafo[maxn];

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

		ll x = soma[v]-(ll)num[u];

		for (int i = 0; i <= c; i++)
		{
			dp[v][i][0] = max(dp[u][i][0], dp[u][i][1]);

			if (!i) continue;

			dp[v][i][1] = dp[u][i-1][0];
			dp[v][i][1] = x+max(dp[v][i][1], dp[u][i-1][1]);
		}

		dfs(v, u);
	}
}

ll solve_big(void)
{
	dp[1][1][1] = soma[1];

	dfs(1, 0);

	ll ans = 0LL;

	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= c; j++)
			ans = max({ans, dp[i][j][0], dp[i][j][1]});

	return ans;
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> c;

	for (int i = 1; i <= n; i++)
		cin >> num[i];

	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;

		grafo[u].push_back(v); grafo[v].push_back(u);
	}

	for (int u = 1; u <= n; u++)
		for (auto v: grafo[u])
			soma[u] += (ll)num[v];

	if (n > 1000)
	{
		cout << solve_big() << "\n";
		return 0;
	}

	ll ans = 0LL;

	for (int i = 1; i <= n; i++)
	{
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= c; j++)
				dp[i][j][0] = dp[i][j][1] = 0LL;

		dp[i][1][1] = soma[i];

		dfs(i, 0);

		for (int j = 1; j <= n; j++)
			for (int l = 0; l <= c; l++)
				ans = max({ans, dp[j][l][0], dp[j][l][1]});
	}

	cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 494 ms 4552 KB Output is correct
8 Correct 54 ms 4480 KB Output is correct
9 Correct 44 ms 4608 KB Output is correct
10 Correct 506 ms 4600 KB Output is correct
11 Correct 231 ms 4480 KB Output is correct
12 Correct 97 ms 4600 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 183132 KB Output is correct
2 Correct 331 ms 183364 KB Output is correct
3 Correct 239 ms 179564 KB Output is correct
4 Correct 305 ms 179288 KB Output is correct
5 Correct 333 ms 179320 KB Output is correct
6 Correct 380 ms 179444 KB Output is correct
7 Correct 320 ms 179296 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 494 ms 4552 KB Output is correct
8 Correct 54 ms 4480 KB Output is correct
9 Correct 44 ms 4608 KB Output is correct
10 Correct 506 ms 4600 KB Output is correct
11 Correct 231 ms 4480 KB Output is correct
12 Correct 97 ms 4600 KB Output is correct
13 Correct 299 ms 183132 KB Output is correct
14 Correct 331 ms 183364 KB Output is correct
15 Correct 239 ms 179564 KB Output is correct
16 Correct 305 ms 179288 KB Output is correct
17 Correct 333 ms 179320 KB Output is correct
18 Correct 380 ms 179444 KB Output is correct
19 Correct 320 ms 179296 KB Output is correct
20 Incorrect 328 ms 181600 KB Output isn't correct
21 Halted 0 ms 0 KB -