Submission #66821

#	Time	Username	Problem	Language	Result	Execution time	Memory
66821		Abelyan	Chase (CEOI17_chase)	C++17	20 / 100	539 ms	101040 KiB

chase

#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
const int N = 100006, V = 106;
const long long INF = (ll)1000000000000000007;
const ll P = 13084673;

ll dp[N][V],p[N],n,k;
bool col[N];
vector<int> g[N];
void dfs(int v,int par=-1) {
	col[v] = true;
	for (int i = 0; i < g[v].size(); i++) {
		int to = g[v][i];
		if (to==par)continue;
		dfs(to,v);
	}
	dp[0][v] = 0;
	for (int i = 1; i <= k; i++) {
		dp[v][i] =0;
		ll mx = 0,sum=0,mx2=0;
		for (int j = 0; j < g[v].size(); j++) {
			int to = g[v][j];
			if (to==par)continue;
			mx = max(mx, dp[to][i]);
			sum += p[to];
			mx2 = max(mx2, dp[to][i - 1]);
		}
		dp[v][i] += max(mx, sum + mx2);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	ll mx = 0;
	if (n <= 1000) {
		for (int i = 1; i <= n; i++) {
			dfs(i);
			mx = max(mx, dp[i][k]);
			//cout << dp[i][k] << endl;
		}
		//assert(mx <= INT_MAX);
		cout << mx << endl;
	}
	else {
		dfs(1);
		cout << dp[1][k] << endl;
	}
	system("pause");
	return 0;
}
/*
5 2
5 3 1 7 6
1 2
1 3
2 4
2 5

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

Compilation message (stderr)

chase.cpp: In function 'void dfs(int, int)':
chase.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++) {
                  ~~^~~~~~~~~~~~~
chase.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < g[v].size(); j++) {
                   ~~^~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:65:8: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
  system("pause");
  ~~~~~~^~~~~~~~~

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