oj.uz

Submission #924158

# Submission time Handle Problem Language Result Execution time Memory
924158 2024-02-08T15:12:34 Z NK_ Chase (CEOI17_chase) C++17
0 / 100
 184 ms 184380 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;
 
ll up[nax][kax], dwn[nax][kax];

int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int N, K; cin >> N >> K;
	vi 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);

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

	// up includes u, while dwn does not
	function<void(int, int)> gen = [&](int u, int p) {
		// cout << u << " " << p << endl;

		vi chd;
		for(auto& v : adj[u]) if (v != p) {
			gen(v, u); chd.pb(v); 
			for(int k = 1; k <= K; k++) {
				up[u][k] = max({up[u][k], up[v][k], up[v][k - 1] + P[u] - A[v]});
				dwn[u][k] = max({dwn[u][k], dwn[v][k], dwn[v][k - 1] + P[v] - A[u]});
				ans = max({ans, up[u][k], dwn[u][k]});
			}
		}


		vl PMX(sz(chd)), SMX(sz(chd));
		for(int k = 0; k <= K; k++) {
			for(int i = 0; i < sz(chd); i++) {
				PMX[i] = dwn[i][k], SMX[sz(chd) - 1 - i] = dwn[i][k];
			}

			for(int i = 1; i < sz(chd); i++) PMX[i] = max(PMX[i - 1], PMX[i]);
			for(int i = sz(chd) - 2; i >= 0; i--) SMX[i] = max(SMX[i + 1], SMX[i]);

			for(int i = 0; i < sz(chd); i++) {
				int v = chd[i];

				ll DWN = 0;
				if (i - 1 >= 0) DWN = max(DWN, PMX[i]);
				if (i + 1 < sz(chd)) DWN = max(DWN, SMX[i]);

				ans = max(ans, DWN + up[v][K - k]);
			}
		}
	};
	
	gen(0, -1);
 
	cout << ans << nl;
 
	exit(0-0);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 164692 KB Output is correct
2 Incorrect 20 ms 164700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 164692 KB Output is correct
2 Incorrect 20 ms 164700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 164692 KB Output is correct
2 Incorrect 20 ms 164700 KB Output isn't correct
3 Halted 0 ms 0 KB -