oj.uz

Submission #924210

# Submission time Handle Problem Language Result Execution time Memory
924210 2024-02-08T16:26:10 Z NK_ Chase (CEOI17_chase) C++17
100 / 100
 280 ms 188116 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
 
using ll = int64_t;
template<class T> using V = vector<T>;
using vl = V<ll>;
using vi = V<int>;

const int nax = 1e5+5;
const int kax = 105;
const ll INFL = 1e18;
 
ll up[nax][kax], dwn[nax][kax];

int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int N, K; cin >> N >> K;
	vl A(N); for(auto& x : A) cin >> x;
 
	vl P(N);
	V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		
		adj[u].pb(v);
		adj[v].pb(u);

		P[u] += A[v]; 
		P[v] += A[u];
	}
 
	ll ans = 0;

	memset(up, 0, sizeof up);
	memset(dwn, 0, sizeof dwn);

	if (K > 0) for(int i = 0; i < N; i++) up[i][1] = P[i];

	// up includes u, while dwn does not
	V<vl> bst(K + 1, vl(4, -1));
	function<void(int, int)> gen = [&](int u, int p) {
		// cout << u << " " << p << endl;

		auto UPV = [&] (int v, int k) { 
			if (v == -1) return ll(min(1, k) * P[u]);
			return max(up[v][k], up[v][k - 1] + P[u] - A[v]); 
		};

		auto DWNV = [&](int v, int k) { 
			if (v == -1) return ll(0);
			return max(dwn[v][k], dwn[v][k - 1] + P[v] - A[u]); 
		};

		vi chd;
		for(auto& v : adj[u]) if (v != p) {
			gen(v, u); chd.pb(v);
		}

		for(auto& v : chd) {
			for(int k = 1; k <= K; k++) {
				up[u][k] = max(up[u][k], UPV(v, k));
				dwn[u][k] = max(dwn[u][k], DWNV(v, k));

				if (UPV(bst[k][1], k) < UPV(v, k)) {
					bst[k][1] = v;
					if (UPV(bst[k][0], k) < UPV(bst[k][1], k)) swap(bst[k][1], bst[k][0]);
				}

				if (DWNV(bst[k][3], k) < DWNV(v, k)) {
					bst[k][3] = v;
					if (DWNV(bst[k][2], k) < DWNV(bst[k][3], k)) swap(bst[k][3], bst[k][2]);
				}
			}
		}

		for(int k = 0; k <= K; k++) {
			ans = max({ans, up[u][k], dwn[u][k]});

			int nk = K - k;

			// k -> up, nk -> dwn
			for(int x = 0; x < 2; x++) for(int y = 2; y < 4; y++) {
				if (bst[k][x] == bst[nk][y]) continue;
				ans = max(ans, UPV(bst[k][x], k) + DWNV(bst[nk][y], nk));
			}

			bst[k][0] = bst[k][1] = bst[nk][2] = bst[nk][3] = -1;
		}
	};
	
	gen(0, -1);
 
	cout << ans << nl;
 
	exit(0-0);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 164688 KB Output is correct
2 Correct 20 ms 164700 KB Output is correct
3 Correct 20 ms 164836 KB Output is correct
4 Correct 20 ms 164696 KB Output is correct
5 Correct 20 ms 164832 KB Output is correct
6 Correct 19 ms 164700 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 164688 KB Output is correct
2 Correct 20 ms 164700 KB Output is correct
3 Correct 20 ms 164836 KB Output is correct
4 Correct 20 ms 164696 KB Output is correct
5 Correct 20 ms 164832 KB Output is correct
6 Correct 19 ms 164700 KB Output is correct
7 Correct 22 ms 164968 KB Output is correct
8 Correct 22 ms 165036 KB Output is correct
9 Correct 21 ms 164688 KB Output is correct
10 Correct 22 ms 164688 KB Output is correct
11 Correct 21 ms 164692 KB Output is correct
12 Correct 20 ms 164700 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 185936 KB Output is correct
2 Correct 260 ms 188104 KB Output is correct
3 Correct 180 ms 175048 KB Output is correct
4 Correct 78 ms 173904 KB Output is correct
5 Correct 280 ms 173972 KB Output is correct
6 Correct 270 ms 174108 KB Output is correct
7 Correct 272 ms 173908 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 164688 KB Output is correct
2 Correct 20 ms 164700 KB Output is correct
3 Correct 20 ms 164836 KB Output is correct
4 Correct 20 ms 164696 KB Output is correct
5 Correct 20 ms 164832 KB Output is correct
6 Correct 19 ms 164700 KB Output is correct
7 Correct 22 ms 164968 KB Output is correct
8 Correct 22 ms 165036 KB Output is correct
9 Correct 21 ms 164688 KB Output is correct
10 Correct 22 ms 164688 KB Output is correct
11 Correct 21 ms 164692 KB Output is correct
12 Correct 20 ms 164700 KB Output is correct
13 Correct 253 ms 185936 KB Output is correct
14 Correct 260 ms 188104 KB Output is correct
15 Correct 180 ms 175048 KB Output is correct
16 Correct 78 ms 173904 KB Output is correct
17 Correct 280 ms 173972 KB Output is correct
18 Correct 270 ms 174108 KB Output is correct
19 Correct 272 ms 173908 KB Output is correct
20 Correct 273 ms 174108 KB Output is correct
21 Correct 72 ms 173908 KB Output is correct
22 Correct 276 ms 174104 KB Output is correct
23 Correct 75 ms 173904 KB Output is correct
24 Correct 268 ms 174104 KB Output is correct
25 Correct 182 ms 174732 KB Output is correct
26 Correct 265 ms 188028 KB Output is correct
27 Correct 272 ms 188116 KB Output is correct