oj.uz

Submission #682169

# Submission time Handle Problem Language Result Execution time Memory
682169 2023-01-16T02:57:57 Z GusterGoose27 Chase (CEOI17_chase) C++11
100 / 100
 1004 ms 171748 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5;
const int MAXV = 101;
ll dp[2][MAXN][MAXV]; // away or towards
int val[MAXN];
ll adj_sum[MAXN];
vector<int> edges[MAXN];
bool vis[MAXN];
int sz[MAXN];
int n, v;
ll ans = 0;

void dfs(int cur, int p = -1) {
	if (p != -1) {
		for (int j = 1; j <= v; j++) {
			dp[0][cur][j] = adj_sum[cur]-val[p];
			dp[1][cur][j] = adj_sum[cur];
		}
	}
	for (int nxt: edges[cur]) {
		if (nxt == p || vis[nxt]) continue;
		dfs(nxt, cur);
		if (p != -1) {
			for (int j = 1; j <= v; j++) {
				dp[0][cur][j] = max(dp[0][cur][j], max(dp[0][nxt][j], dp[0][nxt][j-1]+adj_sum[cur]-val[p]));
				dp[1][cur][j] = max(dp[1][cur][j], max(dp[1][nxt][j], dp[1][nxt][j-1]+adj_sum[cur]-val[nxt]));
			}
		}
	}
}

void get_sz(int cur, int p = -1) {
	sz[cur] = 1;
	for (int nxt: edges[cur]) {
		if (nxt == p || vis[nxt]) continue;
		get_sz(nxt, cur);
		sz[cur] += sz[nxt];
	}
}

void decomp(int cur) {
	get_sz(cur);
	int p = -1;
	int tot_sz = sz[cur];
	bool found = 1;
	while (found) {
		found = 0;
		for (int nxt: edges[cur]) {
			if (nxt == p || vis[nxt]) continue;
			if (sz[nxt] > tot_sz/2) {
				found = 1;
				p = cur;
				cur = nxt;
				break;
			}
		}
	}
	vis[cur] = 1;
	dfs(cur);
	fill(dp[1][cur]+1, dp[1][cur]+v+1, adj_sum[cur]);
	for (int nxt: edges[cur]) {
		if (vis[nxt]) continue;
		for (int i = 0; i <= v; i++) {
			ans = max(ans, dp[1][cur][i]+dp[0][nxt][v-i]);
			if (i) dp[1][cur][i] = max(dp[1][cur][i], max(dp[1][nxt][i], dp[1][nxt][i-1]+adj_sum[cur]-val[nxt]));
		}
	}
	fill(dp[1][cur]+1, dp[1][cur]+v+1, adj_sum[cur]);
	for (int j = edges[cur].size()-1; j >= 0; j--) {
		int nxt = edges[cur][j];
		if (vis[nxt]) continue;
		for (int i = 0; i <= v; i++) {
			ans = max(ans, dp[1][cur][i]+dp[0][nxt][v-i]);
			if (i) dp[1][cur][i] = max(dp[1][cur][i], max(dp[1][nxt][i], dp[1][nxt][i-1]+adj_sum[cur]-val[nxt]));
		}
	}
	ans = max(ans, dp[1][cur][v]);
	// cerr << cur << " "<< ans << "\n";
	for (int nxt: edges[cur]) if (!vis[nxt]) decomp(nxt);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> v;
	for (int i = 0; i < n; i++) cin >> val[i];
	for (int i = 0; i < n-1; i++) {
		int a, b; cin >> a >> b;
		a--; b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
		adj_sum[a] += val[b];
		adj_sum[b] += val[a];
	}
	decomp(0);
	cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2712 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2712 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 6 ms 4308 KB Output is correct
8 Correct 4 ms 4364 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 4 ms 4308 KB Output is correct
11 Correct 4 ms 4308 KB Output is correct
12 Correct 3 ms 4308 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 169508 KB Output is correct
2 Correct 1004 ms 169600 KB Output is correct
3 Correct 181 ms 165892 KB Output is correct
4 Correct 214 ms 165572 KB Output is correct
5 Correct 659 ms 165668 KB Output is correct
6 Correct 702 ms 165708 KB Output is correct
7 Correct 719 ms 165680 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2712 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 6 ms 4308 KB Output is correct
8 Correct 4 ms 4364 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 4 ms 4308 KB Output is correct
11 Correct 4 ms 4308 KB Output is correct
12 Correct 3 ms 4308 KB Output is correct
13 Correct 949 ms 169508 KB Output is correct
14 Correct 1004 ms 169600 KB Output is correct
15 Correct 181 ms 165892 KB Output is correct
16 Correct 214 ms 165572 KB Output is correct
17 Correct 659 ms 165668 KB Output is correct
18 Correct 702 ms 165708 KB Output is correct
19 Correct 719 ms 165680 KB Output is correct
20 Correct 666 ms 167888 KB Output is correct
21 Correct 100 ms 9932 KB Output is correct
22 Correct 714 ms 167764 KB Output is correct
23 Correct 203 ms 167728 KB Output is correct
24 Correct 691 ms 167780 KB Output is correct
25 Correct 191 ms 167680 KB Output is correct
26 Correct 917 ms 171748 KB Output is correct
27 Correct 956 ms 171644 KB Output is correct