oj.uz

Submission #1052478

# Submission time Handle Problem Language Result Execution time Memory
1052478 2024-08-10T14:58:49 Z TAhmed33 Chase (CEOI17_chase) C++
0 / 100
 757 ms 178612 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
ll dp[MAXN][101], p[MAXN], ans[MAXN], s[MAXN];
ll dp2[MAXN][101];
vector <int> adj[MAXN];
int n, v; 
ll mx = 0;
void dfs (int pos, int par) {
	for (auto j : adj[pos]) {
		if (j != par) {
			dfs(j, pos);
		}
	}
	vector <pair <ll, ll>> ii[v + 1];
	vector <pair <ll, ll>> ii2[v + 1];
	ii[0].push_back({0, 0}); ii2[0].push_back({0, 0});
	ii[0].push_back({0, 0}); ii2[0].push_back({0, 0});
	for (int i = 1; i <= v; i++) {
		dp[pos][i] = 0; dp2[pos][i] = 0;
		for (auto j : adj[pos]) {
			if (j != par) {
				ll x = max(dp[j][i], dp[j][i - 1] + s[j] - p[pos]);
				dp[pos][i] = max(dp[pos][i], x);
				ii[i].push_back({x, j});
				x = max(dp2[j][i], dp2[j][i - 1] + s[pos] - p[j]);
				dp2[pos][i] = max(dp2[pos][i], x);
				ii2[i].push_back({x, j});
			}
		}
		dp2[pos][i] = max(dp2[pos][i], s[pos]);
		ii2[i].push_back({s[pos], 0});
	}
	for (int i = 1; i <= v; i++) {
		sort(ii[i].begin(), ii[i].end());
		sort(ii2[i].begin(), ii2[i].end());
	}
	for (int i = 0; i <= v; i++) {
		for (auto j : adj[pos]) {
			if (j == par) continue;
			if (j == ii[i].back().second) {
				mx = max(mx, ii[i][int(ii[i].size()) - 2].first + dp2[j][v - i]);
			} else {
				mx = max(mx, dp[pos][i] + dp2[j][v - i]);
			}
		}
	}
}
void solve () {
	cin >> n >> v;
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		s[a] += p[b]; s[b] += p[a];
	}
	dfs(1, -1);
	cout << mx << '\n';
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Incorrect 1 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Incorrect 1 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 757 ms 178612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Incorrect 1 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -