oj.uz

Submission #1081699

# Submission time Handle Problem Language Result Execution time Memory
1081699 2024-08-30T09:23:04 Z vuavisao Chase (CEOI17_chase) C++14
20 / 100
 363 ms 524288 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 100'000 + 10;

int n, breads;
int pigeons[N];
vector<int> g[N];

namespace sub1 {
	bool check() {
		return (n <= 10);
	}

	int parent[N];
	ll curPigeons[N];

	ll getDiff(int u, ll cur) {
		ll after = 0;
		while (u != 0) {
			after += curPigeons[u];
			u = parent[u];
		}
		return abs(after - cur);
	}

	ll dfs(int u, ll cur, int use) {
		ll res = 0;
		// doesn't drop the breadcrumb
		cur += curPigeons[u];
		res = max(res, getDiff(u, cur));
		for (const auto& v : g[u]) {
			if (v == parent[u]) continue;
			parent[v] = u;
			res = max(res, dfs(v, cur, use));
		}

		// drop the breadcrumb
		if (use < breads) {
			vector<ll> oldPigeons(n + 1, 0);
			oldPigeons[u] = curPigeons[u];
			for (const auto& v : g[u]) {
				oldPigeons[v] = curPigeons[v];
			}
			for (const auto& v : g[u]) {
				curPigeons[u] += curPigeons[v];
				curPigeons[v] = 0;
			}

			res = max(res, getDiff(u, cur));
			
			for (const auto& v : g[u]) {
				if (v == parent[u]) continue;
				parent[v] = u;
				res = max(res, dfs(v, cur, use + 1));
			}

			curPigeons[u] = oldPigeons[u];
			for (const auto& v : g[u]) {
				curPigeons[v] = oldPigeons[v];
			}
		}
		return res;
	}

	void solve() {
		ll res = 0;
		for (int root = 1; root <= n; ++ root) {
			for (int u = 1; u <= n; ++ u) {
				curPigeons[u] = pigeons[u];
				parent[u] = 0;
			}
			res = max(res, dfs(root, 0, 0));
		}
		cout << res;
	}
}

namespace sub2 {
	bool check() {
		return (n <= 1'000);
	}

	ll dp[N][110];

	void dfs(int u, int p) {
		ll bonus = -pigeons[p];
		for (const auto& v : g[u]) {
			bonus += pigeons[v];
		}
		for (int use = breads - 1; use >= 0; -- use) {
			dp[u][use + 1] = max(dp[u][use + 1], dp[u][use] + bonus);
		}
		for (const auto& v : g[u]) {
			if (v == p) continue;
			for (int use = 0; use <= breads; ++ use) {
				dp[v][use] = max(dp[v][use], dp[u][use]);
			}
			dfs(v, u);
		}
	}

	ll calc(int root) {
		for (int u = 0; u <= n + 1; ++ u) {
			for (int use = 0; use <= breads + 1; ++ use) {
				dp[u][use] = 0;
			}
		}
		dfs(root, 0);
		ll res = 0;
		for (int u = 1; u <= n; ++ u) {
			for (int use = 0; use <= breads; ++ use) {
				res = max(res, dp[u][use]);
			}
		}
		return res;
	}

	void solve() {
		ll res = 0;
		for (int root = 1; root <= n; ++ root) {
			res = max(res, calc(root));
		}
		cout << res;
	}
}

namespace sub4 {
	pair<ll, int> dpOut[N][110][2];
	pair<ll, int> dpIn[N][110][2];
	ll cost[N];
	ll res = 0;

	ll getCost(int u, int p) {
		return cost[u] - pigeons[p];
	}

	void update(pair<ll, int> old[], pair<ll, int> val) {
		pair<ll, int> cur = old[0];
		if (val.first >= old[0].first) {
			old[0] = val;
			old[1] = max(old[1], cur);
		}
		else {
			old[1] = max(old[1], val);
		}
	}

	void calc(pair<ll, int> in, pair<ll, int> out) {
		if (in.second == out.second) return;
		res = max(res, in.first + out.first);
	}

	// from child -> u
	void dfsInOut(int u, int p) {
		for (int use = 0; use <= breads; ++ use) {
			dpOut[u][use][0] = (use == 0 ? make_pair(0ll, u) : make_pair(getCost(u, 0), u));
		}
		for (const auto& v : g[u]) {
			if (v == p) continue;
			dfsInOut(v, u);
			
			for (int use = 0; use <= breads; ++ use) {
				pair<ll, int> cur = make_pair(dpOut[v][use][0].first, v);
				update(dpOut[u][use], cur);
				if (use < breads) {
					pair<ll, ll> best = make_pair(dpOut[v][use][0].first + getCost(u, v), v);
					update(dpOut[u][use + 1], best);
				}
			}

			for (int use = 0; use <= breads; ++ use) {
				pair<ll, int> cur = make_pair(dpIn[v][use][0].first, v);
				update(dpIn[u][use], cur);
				if (use < breads) {
					pair<ll, ll> best = make_pair(dpIn[v][use][0].first + getCost(v, u), v);
					update(dpIn[u][use + 1], best);
				}
			}
		}

		for (int useIn = 0; useIn <= breads; ++ useIn) {
			int useOut = breads - useIn;
			for (int typeOut = 0; typeOut < 2; ++ typeOut) {
				for (int typeIn = 0; typeIn < 2; ++ typeIn) {
					calc(dpOut[u][useOut][typeOut], dpIn[u][useIn][typeIn]);
				}
			}
		}
	}

	void solve() {
		for (int u = 1; u <= n; ++ u) {
			for (const auto& v : g[u]) {
				cost[u] += pigeons[v];
			}
		}
		dfsInOut(1, 0);
		// cerr << getCost(6, 0) + getCost(7, 6) << '\n';
		// cerr << dpIn[7][1][0].first << '\n';
		for (int u = 1; u <= n; ++ u) {
			for (int use = breads - 1; use >= 0; -- use) {
				dpIn[u][use + 1][0].first = max(dpIn[u][use + 1][0].first, dpIn[u][use][0].first + getCost(u, 0));
			}
			for (int use = 0; use <= breads; ++ use) {
				res = max(res, dpIn[u][use][0].first);
				res = max(res, dpOut[u][use][0].first);
				// cerr << u << ' ' << use << ' ' << dpIn[u][use][0].first << '\n';
			}
		}
		cout << res;
	}
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n >> breads;
	for (int u = 1; u <= n; ++ u) cin >> pigeons[u];
	for (int i = 2; i <= n; ++ i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	// if (sub1::check()) {
	// 	sub1::solve();
	// 	return 0;
	// }
	// if (sub2::check()) {
	// 	sub2::solve();
	// 	return 0;
	// }
	// cout << sub2::calc(1);
	sub4::solve();
	return (0 ^ 0);
}

/// Code by vuavisao

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 1 ms 5976 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 1 ms 5980 KB Output is correct
6 Correct 1 ms 5980 KB Output is correct
7 Correct 6 ms 11608 KB Output is correct
8 Correct 4 ms 11612 KB Output is correct
9 Correct 3 ms 11356 KB Output is correct
10 Correct 5 ms 11356 KB Output is correct
11 Correct 4 ms 11352 KB Output is correct
12 Incorrect 4 ms 11356 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 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 2 ms 5976 KB Output is correct
2 Correct 1 ms 5976 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 1 ms 5980 KB Output is correct
6 Correct 1 ms 5980 KB Output is correct
7 Correct 6 ms 11608 KB Output is correct
8 Correct 4 ms 11612 KB Output is correct
9 Correct 3 ms 11356 KB Output is correct
10 Correct 5 ms 11356 KB Output is correct
11 Correct 4 ms 11352 KB Output is correct
12 Incorrect 4 ms 11356 KB Output isn't correct
13 Halted 0 ms 0 KB -