oj.uz

Submission #293881

# Submission time Handle Problem Language Result Execution time Memory
293881 2020-09-08T13:27:18 Z shivensinha4 Chase (CEOI17_chase) C++17
100 / 100
 812 ms 455720 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
 
const int MXN = 1e5, MXV = 100;
int n, v;
ll dp[MXN+1][MXV+1];
ll nums[MXN+1];
vi adj[MXN+1];
ll ans = 0;
 
void prefMax(vector<ll> &k) {
	for_(i, 1, k.size()) k[i] = max(k[i], k[i-1]);
}
 
void sufMax(vector<ll> &k) {
	for (int i = k.size()-2; i >= 0; i--) k[i] = max(k[i], k[i+1]);
}
 
void init(int p, int parent) {
	ll s = 0;
	for (int i: adj[p]) if (i != parent) {
		init(i, p);
		s += nums[i];
	}
	for_(ct, 0, v+1) {
		ll take = 0, noTake = 0;
		for (int i: adj[p]) if (i != parent) {
			if (ct) take = max(take, dp[i][ct-1]);
			noTake = max(noTake, dp[i][ct]);
		}
		dp[p][ct] = noTake;
		if (ct) dp[p][ct] = max(dp[p][ct], s+take);
	}
}
 
void reroot(int p, int parent, vector<ll> &pVal) {
	int ch = adj[p].size();
	
	ll s = 0;
	for_(i, 0, ch) s += nums[adj[p][i]];
	vector<pair<ll, int>> mxTake(v+1), mmxTake(v+1), mxNoTake(v+1), mmxNoTake(v+1);
	
	for_(ct, 0, v+1) {
		for (int i: adj[p]) {
			ll take = 0, noTake = 0;
			if (i != parent) {
				take = dp[i][ct];
				noTake = dp[i][ct];
			} else {
				take = pVal[ct];
				noTake = pVal[ct];
			}
			if (take >= mxTake[ct].first) {
				swap(mxTake[ct], mmxTake[ct]);
				mxTake[ct] = {take, i};
			} else if (take > mmxTake[ct].first) {
				mmxTake[ct] = {take, i};
			}
			
			if (noTake >= mxNoTake[ct].first) {
				swap(mxNoTake[ct], mmxNoTake[ct]);
				mxNoTake[ct] = {noTake, i};
			} else if (noTake > mmxNoTake[ct].first) {
				mmxNoTake[ct] = {noTake, i};
			}
		}
	}
	
	ans = max({ans, mxTake[v-1].first + s, mxNoTake[v].first});
	for_(i, 0, ch) if (adj[p][i] != parent) {
		vector<ll> temp(v+1);
		for_(ct, 0, v+1) {
			ll nt = mxNoTake[ct].first, t;
			if (ct) t = mxTake[ct-1].first;
			if (mxNoTake[ct].second == adj[p][i]) nt = mmxNoTake[ct].first;
			if (ct and mxTake[ct-1].second == adj[p][i]) t = mmxTake[ct-1].first;
			
			temp[ct] = nt;
			if (ct) {
				ll nv = t + s - nums[adj[p][i]];
				temp[ct] = max(temp[ct], nv);
			}
		}
		reroot(adj[p][i], p, temp);
	}
}
 
int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> v;
	for_(i, 0, n) cin >> nums[i];
	for_(i, 0, n-1) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	
	if (v == 0) {
		cout << 0 << endl;
		return 0;
	}
	
	init(0, 0);
	vector<ll> useless;
	reroot(0, 0, useless);
	
	cout << ans << endl;
 
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 13 ms 7296 KB Output is correct
8 Correct 4 ms 3840 KB Output is correct
9 Correct 3 ms 3584 KB Output is correct
10 Correct 7 ms 3712 KB Output is correct
11 Correct 4 ms 3584 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 452808 KB Output is correct
2 Correct 759 ms 450808 KB Output is correct
3 Correct 670 ms 88304 KB Output is correct
4 Correct 199 ms 87800 KB Output is correct
5 Correct 545 ms 88344 KB Output is correct
6 Correct 499 ms 88216 KB Output is correct
7 Correct 403 ms 88224 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 13 ms 7296 KB Output is correct
8 Correct 4 ms 3840 KB Output is correct
9 Correct 3 ms 3584 KB Output is correct
10 Correct 7 ms 3712 KB Output is correct
11 Correct 4 ms 3584 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct
13 Correct 800 ms 452808 KB Output is correct
14 Correct 759 ms 450808 KB Output is correct
15 Correct 670 ms 88304 KB Output is correct
16 Correct 199 ms 87800 KB Output is correct
17 Correct 545 ms 88344 KB Output is correct
18 Correct 499 ms 88216 KB Output is correct
19 Correct 403 ms 88224 KB Output is correct
20 Correct 483 ms 88064 KB Output is correct
21 Correct 58 ms 8828 KB Output is correct
22 Correct 419 ms 88228 KB Output is correct
23 Correct 170 ms 87800 KB Output is correct
24 Correct 404 ms 88184 KB Output is correct
25 Correct 647 ms 87748 KB Output is correct
26 Correct 812 ms 455720 KB Output is correct
27 Correct 798 ms 455672 KB Output is correct