oj.uz

Submission #924179

# Submission time Handle Problem Language Result Execution time Memory
924179 2024-02-08T15:54:45 Z NK_ Chase (CEOI17_chase) C++17
20 / 100
 321 ms 186488 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) 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 -INFL;
			return max(up[v][k], up[v][k - 1] + P[u] - A[v]); 
		};

		auto DWNV = [&](int v, int k) { 
			if (v == -1) return -INFL;
			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));

				ans = max({ans, up[u][k], dwn[u][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++) {
			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 20 ms 165056 KB Output is correct
2 Correct 24 ms 164700 KB Output is correct
3 Correct 36 ms 164636 KB Output is correct
4 Correct 21 ms 164688 KB Output is correct
5 Correct 20 ms 164700 KB Output is correct
6 Correct 20 ms 164688 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 165056 KB Output is correct
2 Correct 24 ms 164700 KB Output is correct
3 Correct 36 ms 164636 KB Output is correct
4 Correct 21 ms 164688 KB Output is correct
5 Correct 20 ms 164700 KB Output is correct
6 Correct 20 ms 164688 KB Output is correct
7 Incorrect 24 ms 164956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 165056 KB Output is correct
2 Correct 24 ms 164700 KB Output is correct
3 Correct 36 ms 164636 KB Output is correct
4 Correct 21 ms 164688 KB Output is correct
5 Correct 20 ms 164700 KB Output is correct
6 Correct 20 ms 164688 KB Output is correct
7 Incorrect 24 ms 164956 KB Output isn't correct
8 Halted 0 ms 0 KB -