oj.uz

Submission #848555

# Submission time Handle Problem Language Result Execution time Memory
848555 2023-09-12T21:54:55 Z qthang2k11 Chase (CEOI17_chase) C++17
40 / 100
 440 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int N = 1e5 + 5;
 
template<class X, class Y>
inline void maxi(X &x, Y y) {
	if (x < y) x = y;
}
 
vector<int> g[N];
int n, k, a[N];
ll s[N];
 
ll ans = 0;
 
struct Node {
	ll val[101][2];
	
	Node() { 
		memset(val, -63, sizeof val); 
	}
	
	void maxi_(const Node &other) {
		for (int i = 0; i <= k; i++)
			for (int j = 0; j < 2; j++)
				maxi(val[i][j], other.val[i][j]);
	}
	
	void deal(const Node &other, const int &x, const int &y) { // update from y to x
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				ll cur = other.val[i][j];
				if (i < k) {
					if (j) maxi(val[i + 1][1], cur + s[x] - a[y]);
					else maxi(val[i + 1][1], cur + s[x] - a[y]);
				}
				maxi(val[i][0], cur);
			}
		}
	}
	
	Node deal_(const int &x, const int &y) { // update from y to x
		Node ans;
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				ll cur = val[i][j];
				if (i < k) {
					if (j) maxi(ans.val[i + 1][1], cur + s[x] - a[y]);
					else maxi(ans.val[i + 1][1], cur + s[x] - a[y]);
				}
				maxi(ans.val[i][0], cur);
			}
		}
		return ans;
	}
	
	ll res() const {
		ll ans = 0;
		for (int i = 0; i <= k; i++)
			for (int j = 0; j < 2; j++)
				maxi(ans, val[i][j]);
		return ans;
	}
 
};
 
Node dp[N], pref, suf[N];
 
void dfs_init(int x, int p) {
	for (int i = g[x].size() - 1; i >= 0; i--) {
		int y = g[x][i];
		if (y != p) continue;
		swap(g[x].back(), g[x][i]);
		g[x].pop_back();
	}
	for (int y: g[x]) 
		dfs_init(y, x);
}
 
void dfs(int x) {
	for (int y: g[x]) {
		dfs(y);
		dp[x].deal(dp[y], x, y);
	}
	maxi(dp[x].val[0][0], 0);
	if (k > 0) maxi(dp[x].val[1][1], s[x]);
	maxi(ans, dp[x].res());
}
 
void dfs_reroot(int x, Node down) {
	maxi(down.val[0][0], 0);
	if (k > 0) maxi(down.val[1][1], s[x]);
	maxi(ans, down.res());
	suf[(int)g[x].size()] = pref = Node();
	for (int o = g[x].size(), i = o - 1; i >= 0; i--) {
		int y = g[x][i];
		suf[i] = suf[i + 1];
		suf[i].deal(dp[y], x, y);
	}
	vector<Node> to_push(g[x].size());
	for (int i = 0, o = g[x].size(); i < o; i++) {
		int y = g[x][i];
		Node cur = down;
		if (i > 0) cur.maxi_(pref);
		if (i + 1 < o) cur.maxi_(suf[i + 1]);
		to_push[i] = cur.deal_(y, x);
		pref.deal(dp[y], x, y);
	}
	for (int i = 0, o = g[x].size(); i < o; i++) {
		int y = g[x][i];
		dfs_reroot(y, to_push[i]);
	}
}
 
int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].emplace_back(y);
		g[y].emplace_back(x);
	}
	for (int x = 1; x <= n; x++) {
		for (int y: g[x])
			s[x] += a[y];
	}
	dfs_init(1, 0);
	dfs(1);
	dfs_reroot(1, Node());
	cout << ans;
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 320080 KB Output is correct
2 Correct 38 ms 320080 KB Output is correct
3 Correct 37 ms 320208 KB Output is correct
4 Correct 38 ms 320080 KB Output is correct
5 Correct 37 ms 320084 KB Output is correct
6 Correct 38 ms 320092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 320080 KB Output is correct
2 Correct 38 ms 320080 KB Output is correct
3 Correct 37 ms 320208 KB Output is correct
4 Correct 38 ms 320080 KB Output is correct
5 Correct 37 ms 320084 KB Output is correct
6 Correct 38 ms 320092 KB Output is correct
7 Correct 42 ms 324180 KB Output is correct
8 Correct 42 ms 324176 KB Output is correct
9 Correct 39 ms 321616 KB Output is correct
10 Correct 40 ms 320348 KB Output is correct
11 Correct 39 ms 320336 KB Output is correct
12 Correct 39 ms 320156 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 440 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 320080 KB Output is correct
2 Correct 38 ms 320080 KB Output is correct
3 Correct 37 ms 320208 KB Output is correct
4 Correct 38 ms 320080 KB Output is correct
5 Correct 37 ms 320084 KB Output is correct
6 Correct 38 ms 320092 KB Output is correct
7 Correct 42 ms 324180 KB Output is correct
8 Correct 42 ms 324176 KB Output is correct
9 Correct 39 ms 321616 KB Output is correct
10 Correct 40 ms 320348 KB Output is correct
11 Correct 39 ms 320336 KB Output is correct
12 Correct 39 ms 320156 KB Output is correct
13 Runtime error 440 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -