oj.uz

Submission #293896

# Submission time Handle Problem Language Result Execution time Memory
293896 2020-09-08T13:35:39 Z shivensinha4 Chase (CEOI17_chase) C++17
100 / 100
 850 ms 453624 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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 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;
}

Compilation message

chase.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
chase.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 450684 KB Output is correct
2 Correct 850 ms 448632 KB Output is correct
3 Correct 603 ms 86124 KB Output is correct
4 Correct 159 ms 85840 KB Output is correct
5 Correct 385 ms 86144 KB Output is correct
6 Correct 398 ms 86232 KB Output is correct
7 Correct 401 ms 86164 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 9 ms 7168 KB Output is correct
8 Correct 4 ms 3840 KB Output is correct
9 Correct 3 ms 3584 KB Output is correct
10 Correct 6 ms 3584 KB Output is correct
11 Correct 4 ms 3488 KB Output is correct
12 Correct 6 ms 3584 KB Output is correct
13 Correct 805 ms 450684 KB Output is correct
14 Correct 850 ms 448632 KB Output is correct
15 Correct 603 ms 86124 KB Output is correct
16 Correct 159 ms 85840 KB Output is correct
17 Correct 385 ms 86144 KB Output is correct
18 Correct 398 ms 86232 KB Output is correct
19 Correct 401 ms 86164 KB Output is correct
20 Correct 413 ms 85976 KB Output is correct
21 Correct 52 ms 6648 KB Output is correct
22 Correct 394 ms 85992 KB Output is correct
23 Correct 176 ms 86032 KB Output is correct
24 Correct 400 ms 86008 KB Output is correct
25 Correct 584 ms 86124 KB Output is correct
26 Correct 770 ms 453624 KB Output is correct
27 Correct 752 ms 453588 KB Output is correct