oj.uz

Submission #784491

# Submission time Handle Problem Language Result Execution time Memory
784491 2023-07-16T07:27:36 Z blue Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 173920 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, up[v1][j] + dn[v2][m-1-j] + wsum[u] - w[v1]);
			}
		}
	}
}





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 3 ms 4736 KB Output is correct
6 Correct 3 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 3 ms 4736 KB Output is correct
6 Correct 3 ms 4564 KB Output is correct
7 Correct 4 ms 6356 KB Output is correct
8 Correct 3 ms 6336 KB Output is correct
9 Correct 17 ms 6228 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 3 ms 6228 KB Output is correct
12 Correct 3 ms 6208 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 173592 KB Output is correct
2 Correct 283 ms 173920 KB Output is correct
3 Execution timed out 4059 ms 167180 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 3 ms 4736 KB Output is correct
6 Correct 3 ms 4564 KB Output is correct
7 Correct 4 ms 6356 KB Output is correct
8 Correct 3 ms 6336 KB Output is correct
9 Correct 17 ms 6228 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 3 ms 6228 KB Output is correct
12 Correct 3 ms 6208 KB Output is correct
13 Correct 250 ms 173592 KB Output is correct
14 Correct 283 ms 173920 KB Output is correct
15 Execution timed out 4059 ms 167180 KB Time limit exceeded
16 Halted 0 ms 0 KB -