oj.uz

Submission #784493

# Submission time Handle Problem Language Result Execution time Memory
784493 2023-07-16T07:28:39 Z blue Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 172896 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
#define sz(x) int(x.size())

const int mx = 100'000;
const int mxv = 100;

int n;
int m;

vll w(1+mx, 0);

vi edge[1+mx];

vi par(1 + mx, 0);

vll wsum(1+mx, 0);

void dfs(int u)
{
	for(int v : edge[u])
	{
		if(par[u] == v)
			continue;

		par[v] = u;
		dfs(v);
	}
}




ll up[1+mx][1+mxv];
ll dn[1+mx][1+mxv];

ll res = 0;

void dfs2(int u)
{
	for(int v : edge[u])
	{
		if(par[u] != v)
			dfs2(v);
	}




	//1. calculate up

	up[u][0] = 0;
	for(int k = 1; k <= m; k++)
		up[u][k] = wsum[u];

	for(int k = 0; k <= m; k++)
	{
		for(int v : edge[u])
		{
			if(par[u] == v)
				continue;

			up[u][k] = max(up[u][k], up[v][k]);
			if(k > 0)
				up[u][k] = max(up[u][k], up[v][k-1] + wsum[u] - w[v]);
		}
	}





	//2. calculate down

	dn[u][0] = 0;
	for(int k = 1; k <= m; k++)
		dn[u][k] = wsum[u] - w[par[u]];

	for(int k = 0; k <= m; k++)
	{
		for(int v : edge[u])
		{
			if(par[u] == v)
				continue;

			dn[u][k] = max(dn[u][k], dn[v][k]);

			if(k > 0)
				dn[u][k] = max(dn[u][k], dn[v][k-1] + wsum[u] - w[par[u]]);
		}
	}



	//3. update res

	//single element
	if(m >= 1)
		res = max(res, wsum[u]);

	//up path
	res = max(res, up[u][m]);

	//down path
	for(int v : edge[u])
	{
		if(par[u] != v)
		{
			res = max(res, dn[v][m]);
			if(m-1 >= 0)
				res = max(res, dn[v][m-1] + wsum[u]);
		}
	}

	//combination
	vll temp(1+m, -1'000'000'000'000'000'000LL);
	// for(int v : edge[u])
	// {
	// 	if(par[u] == v)
	// 		continue;

	// 	for(int j = 0; j <= m; j++)
	// 	{
	// 		res = max(res, temp0[m-j] + dn[v][j]);
	// 		res = max(res, temp1[m-j] + w[v] + dn[v][j]);
	// 	}

	// 	////////
	// 	for(int j = 0; j <= m; j++)
	// 	{
	// 		temp[j] = max(temp[j], up[v][j]);
	// 		if(j >= 1)
	// 		{
	// 			temp1[j] = max(temp1[j], up[v][j-1] + wsum[u] - w[v]);
	// 		}
	// 	}
	// }

	for(int v1 : edge[u])
	{
		if(par[u] == v1)
			continue;

		for(int v2 : edge[u])
		{
			if(par[u] == v2)
				continue;

			if(v1 == v2)
				continue;

			for(int j = 0; j <= m; j++)
			{
				res = max(res, (up[v1][j]) + (dn[v2][m-j]));
			}

			for(int j = 0; j <= m-1; j++)
			{
				res = max(res, (wsum[u]) + (up[v1][j] - w[v1]) + (dn[v2][m-1-j]));
			}
		}
	}
}





int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

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

	for(int e = 1; e <= n-1; e++)
	{
		int a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	dfs(1);

	for(int i = 1; i <= n; i++)
		for(int j : edge[i])
			wsum[i] += w[j];

	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= m; j++)
		{
			up[i][j] = 0;
			dn[i][j] = 0;
		}
	}


	dfs2(1);


	// for(int i = 1; i <= n; i++)
	// {
	// 	for(int j = 0; j <= m; j++)
	// 		cerr << dn[i][j] << ' ';
	// 	cerr << '\n';
	// }

	cout << res << '\n';

}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Correct 2 ms 4564 KB Output is correct
5 Correct 2 ms 4692 KB Output is correct
6 Correct 2 ms 4564 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 16 ms 6228 KB Output is correct
10 Correct 5 ms 6228 KB Output is correct
11 Correct 3 ms 6228 KB Output is correct
12 Correct 3 ms 6228 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 172896 KB Output is correct
2 Correct 258 ms 172896 KB Output is correct
3 Execution timed out 4048 ms 166212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Correct 2 ms 4564 KB Output is correct
5 Correct 2 ms 4692 KB Output is correct
6 Correct 2 ms 4564 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 16 ms 6228 KB Output is correct
10 Correct 5 ms 6228 KB Output is correct
11 Correct 3 ms 6228 KB Output is correct
12 Correct 3 ms 6228 KB Output is correct
13 Correct 254 ms 172896 KB Output is correct
14 Correct 258 ms 172896 KB Output is correct
15 Execution timed out 4048 ms 166212 KB Time limit exceeded
16 Halted 0 ms 0 KB -