oj.uz

답안 #293895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
293895 2020-09-08T13:35:10 Z shivensinha4 Chase (CEOI17_chase) C++17
100 / 100
 1207 ms 461324 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 13 ms 7284 KB Output is correct
8 Correct 4 ms 3968 KB Output is correct
9 Correct 5 ms 3584 KB Output is correct
10 Correct 8 ms 3656 KB Output is correct
11 Correct 7 ms 3584 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1179 ms 458232 KB Output is correct
2 Correct 1160 ms 456184 KB Output is correct
3 Correct 1030 ms 88256 KB Output is correct
4 Correct 196 ms 87808 KB Output is correct
5 Correct 696 ms 88300 KB Output is correct
6 Correct 740 ms 88300 KB Output is correct
7 Correct 724 ms 88224 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 13 ms 7284 KB Output is correct
8 Correct 4 ms 3968 KB Output is correct
9 Correct 5 ms 3584 KB Output is correct
10 Correct 8 ms 3656 KB Output is correct
11 Correct 7 ms 3584 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct
13 Correct 1179 ms 458232 KB Output is correct
14 Correct 1160 ms 456184 KB Output is correct
15 Correct 1030 ms 88256 KB Output is correct
16 Correct 196 ms 87808 KB Output is correct
17 Correct 696 ms 88300 KB Output is correct
18 Correct 740 ms 88300 KB Output is correct
19 Correct 724 ms 88224 KB Output is correct
20 Correct 725 ms 88164 KB Output is correct
21 Correct 70 ms 8860 KB Output is correct
22 Correct 789 ms 88192 KB Output is correct
23 Correct 187 ms 87800 KB Output is correct
24 Correct 700 ms 88248 KB Output is correct
25 Correct 1006 ms 87792 KB Output is correct
26 Correct 1207 ms 461324 KB Output is correct
27 Correct 1130 ms 461180 KB Output is correct