Submission #309579

#	Time	Username	Problem	Language	Result	Execution time	Memory
309579		Kenzo_1114	Chase (CEOI17_chase)	C++17	70 / 100	497 ms	98808 KiB

chase

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int MAXM = 110;

int n, m;
long long int p[MAXN], dp[MAXN][MAXM];
vector<int> graph[MAXN];

void dfs(int v, int par)
{
	long long int sumP = 0;

	for(int i = 0; i < graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == par)	continue;

		sumP += p[u];
		dfs(u, v);
	}

	for(int k = 0; k <= m; k++)
	{
		dp[v][k] = 0;
		for(int i = 0; i < graph[v].size(); i++)
		{
			int u = graph[v][i];
			if(u == par)	continue;

			dp[v][k] = max(dp[v][k], dp[u][k]);
			if(k)	dp[v][k] = max(dp[v][k], dp[u][k - 1] + sumP);
		}
	}
}

int main ()
{
	scanf("%d %d", &n, &m);

	for(int i = 1; i <= n; i++)	scanf("%lld", &p[i]);

	for(int i = 0, u, v; i < n - 1; i++)
	{
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}	

	long long int ans = 0;
	if(n <= 1000)
	{
		for(int i = 1; i <= n; i++)
		{
			dfs(i, i);
			for(int j = 1; j <= n; j++)	ans = max(ans, dp[j][m]);
		}
	}
	else
	{
		dfs(1, 1);
		for(int j = 1; j <= n; j++)		ans = max(ans, dp[j][m]);
	}

	printf("%lld\n", ans);
}

/*

12 2
2 3 3 8 1 5 6 7 8 3 5 4 
2 1
2 7
3 4 
4 7 
7 6 
5 6 
6 8 
6 9
7 10 
10 11 
10 12

*/

Compilation message (stderr)

chase.cpp: In function 'void dfs(int, int)':
chase.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < graph[v].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
chase.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i = 0; i < graph[v].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
chase.cpp:41:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  for(int i = 1; i <= n; i++) scanf("%lld", &p[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~
chase.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30