oj.uz

Submission #853415

# Submission time Handle Problem Language Result Execution time Memory
853415 2023-09-24T10:05:02 Z manizare Chase (CEOI17_chase) C++14
100 / 100
 436 ms 331384 KB 
// [AC, +]
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int N = 1e5 + 5;
 
template<class X, class Y>
inline void maxi(X &x, Y y) {
	if (x < y) x = y;
}
 
vector<int> g[N];
int n, k, a[N];
ll s[N];
 
ll ans = 0, INF;
 
ll up[N][101][2], down[N][101][2], sdown[101][2];
int par[N];
 
void dfs_init(int x, int p) {
	par[x] = p;
	for (int i = g[x].size() - 1; i >= 0; i--) {
		int y = g[x][i];
		if (y != p) continue;
		swap(g[x][i], g[x].back());
		g[x].pop_back();
	}
	for (int y: g[x]) dfs_init(y, x);
}
 
void dfs(int x) {
	up[x][0][0] = down[x][0][0] = 0;
	if (k > 0) {
		up[x][1][1] = s[x];
		down[x][1][0] = s[x] - a[par[x]];
		if (k > 1) down[x][1][1] = s[x] - a[par[x]];
	}
	for (int y: g[x]) {
		dfs(y);
		memset(sdown, -63, sizeof sdown);
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				sdown[i][j] = down[y][i][j];
				if (i) maxi(sdown[i][j], sdown[i - 1][j]);
			}
		}
		for (int i = 0; i <= k; i++) 
			for (int j = 0; j < 2; j++) 
				maxi(ans, up[x][i][j] + sdown[k - i][j]);
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				ll cur = up[y][i][j];
				if (i < k) maxi(up[x][i + 1][1], cur + s[x] - a[y]);
				maxi(up[x][i][0], cur);
			}
		}
		for (int i = 0; i <= k; i++) {
			if (i < k) {
				maxi(down[x][i + 1][1], down[y][i][1] + s[x] - a[par[x]]);
				maxi(down[x][i + 1][0], down[y][i][1] + s[x] - a[par[x]]);
			}
			maxi(down[x][i][1], down[y][i][0]);
			maxi(down[x][i][0], down[y][i][0]);
		}
	}
	for (int i = 0; i <= k; i++) {
		for (int j = 0; j < 2; j++)
			maxi(ans, up[x][i][j]);
		maxi(ans, down[x][i][0]);
	}
	reverse(g[x].begin(), g[x].end());
}
 
int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].emplace_back(y);
		g[y].emplace_back(x);
	}
	for (int x = 1; x <= n; x++) {
		for (int y: g[x])
			s[x] += a[y];
	}
	dfs_init(1, 0);
	memset(up, -63, sizeof up);
	memset(down, -63, sizeof down);
	dfs(1);
	memset(up, -63, sizeof up);
	memset(down, -63, sizeof down);
	dfs(1);
	cout << ans;
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 320344 KB Output is correct
2 Correct 58 ms 320424 KB Output is correct
3 Correct 57 ms 320544 KB Output is correct
4 Correct 57 ms 320336 KB Output is correct
5 Correct 56 ms 320336 KB Output is correct
6 Correct 56 ms 320388 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 320344 KB Output is correct
2 Correct 58 ms 320424 KB Output is correct
3 Correct 57 ms 320544 KB Output is correct
4 Correct 57 ms 320336 KB Output is correct
5 Correct 56 ms 320336 KB Output is correct
6 Correct 56 ms 320388 KB Output is correct
7 Correct 61 ms 320592 KB Output is correct
8 Correct 60 ms 320384 KB Output is correct
9 Correct 56 ms 320460 KB Output is correct
10 Correct 58 ms 320380 KB Output is correct
11 Correct 57 ms 320336 KB Output is correct
12 Correct 57 ms 320348 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 329232 KB Output is correct
2 Correct 395 ms 329200 KB Output is correct
3 Correct 319 ms 324040 KB Output is correct
4 Correct 137 ms 323744 KB Output is correct
5 Correct 435 ms 323840 KB Output is correct
6 Correct 425 ms 323660 KB Output is correct
7 Correct 415 ms 323852 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 320344 KB Output is correct
2 Correct 58 ms 320424 KB Output is correct
3 Correct 57 ms 320544 KB Output is correct
4 Correct 57 ms 320336 KB Output is correct
5 Correct 56 ms 320336 KB Output is correct
6 Correct 56 ms 320388 KB Output is correct
7 Correct 61 ms 320592 KB Output is correct
8 Correct 60 ms 320384 KB Output is correct
9 Correct 56 ms 320460 KB Output is correct
10 Correct 58 ms 320380 KB Output is correct
11 Correct 57 ms 320336 KB Output is correct
12 Correct 57 ms 320348 KB Output is correct
13 Correct 371 ms 329232 KB Output is correct
14 Correct 395 ms 329200 KB Output is correct
15 Correct 319 ms 324040 KB Output is correct
16 Correct 137 ms 323744 KB Output is correct
17 Correct 435 ms 323840 KB Output is correct
18 Correct 425 ms 323660 KB Output is correct
19 Correct 415 ms 323852 KB Output is correct
20 Correct 413 ms 323852 KB Output is correct
21 Correct 128 ms 325712 KB Output is correct
22 Correct 417 ms 325936 KB Output is correct
23 Correct 134 ms 325936 KB Output is correct
24 Correct 415 ms 325940 KB Output is correct
25 Correct 334 ms 325716 KB Output is correct
26 Correct 436 ms 331384 KB Output is correct
27 Correct 423 ms 331384 KB Output is correct