oj.uz

Submission #66821

# Submission time Handle Problem Language Result Execution time Memory
66821 2018-08-12T11:18:39 Z Abelyan Chase (CEOI17_chase) C++17
20 / 100
 539 ms 101040 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 3 ms 2792 KB Output is correct
3 Correct 6 ms 2880 KB Output is correct
4 Correct 5 ms 2948 KB Output is correct
5 Correct 5 ms 3028 KB Output is correct
6 Correct 5 ms 3044 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 3 ms 2792 KB Output is correct
3 Correct 6 ms 2880 KB Output is correct
4 Correct 5 ms 2948 KB Output is correct
5 Correct 5 ms 3028 KB Output is correct
6 Correct 5 ms 3044 KB Output is correct
7 Correct 510 ms 4136 KB Output is correct
8 Correct 50 ms 4136 KB Output is correct
9 Correct 62 ms 4136 KB Output is correct
10 Correct 539 ms 4136 KB Output is correct
11 Correct 196 ms 4136 KB Output is correct
12 Incorrect 79 ms 4276 KB Output isn't correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 96424 KB Output is correct
2 Correct 232 ms 98544 KB Output is correct
3 Correct 410 ms 98544 KB Output is correct
4 Correct 162 ms 98948 KB Output is correct
5 Incorrect 236 ms 101040 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 3 ms 2792 KB Output is correct
3 Correct 6 ms 2880 KB Output is correct
4 Correct 5 ms 2948 KB Output is correct
5 Correct 5 ms 3028 KB Output is correct
6 Correct 5 ms 3044 KB Output is correct
7 Correct 510 ms 4136 KB Output is correct
8 Correct 50 ms 4136 KB Output is correct
9 Correct 62 ms 4136 KB Output is correct
10 Correct 539 ms 4136 KB Output is correct
11 Correct 196 ms 4136 KB Output is correct
12 Incorrect 79 ms 4276 KB Output isn't correct