oj.uz

Submission #391524

# Submission time Handle Problem Language Result Execution time Memory
391524 2021-04-19T07:32:19 Z palilo Dynamite (POI11_dyn) C++17
100 / 100
 701 ms 26800 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
#endif
	int n, m;
	cin >> n >> m;

	vector<bool> d(n);
	for (auto&& x : d) {
		char c;
		cin >> c;
		x = c == '1';
	}

	if (count(d.begin(), d.end(), true) <= m)
		return cout << 0, 0;

	vector<vector<int>> adj(n);
	for (int i = n - 1, u, v; i--;) {
		cin >> u >> v, --u, --v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}

	auto rev_dfn = [&](int src) {
		vector<int> stk = {src}, vtx(n);

		for (int i = 0; i < n; ++i) {
			const auto u = stk.back();
			stk.pop_back();

			vtx[i] = u;
			for (const auto& v : adj[u]) {
				adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
				stk.emplace_back(v);
			}
		}
		reverse(vtx.begin(), vtx.end());
		return vtx;
	}(0);

	// dp_dyn[i] : maximum distance from i to dynamite in sub[i]
	// dp_fus[i] : minimum distance from i to   fuse   in sub[i]
	vector<int> dp_dyn(n), dp_fus(n);

	auto valid = [&](int lim) {
		fill(dp_dyn.begin(), dp_dyn.end(), -1);
		fill(dp_fus.begin(), dp_fus.end(), 0x3f3f3f3f);
		int k = m;

		for (const auto& u : rev_dfn) {
			for (const auto& v : adj[u]) {
				if (~dp_dyn[v]) dp_dyn[u] = max(dp_dyn[u], dp_dyn[v] + 1);
				dp_fus[u] = min(dp_fus[u], dp_fus[v] + 1);
			}
			if (dp_dyn[u] == -1 && d[u]) dp_dyn[u] = 0;

			if (dp_dyn[u] == lim) {
				if (!k--) return false;
				dp_dyn[u] = -1, dp_fus[u] = 0;
			} else if (dp_dyn[u] + dp_fus[u] <= lim)
				dp_dyn[u] = -1;
		}
		return k || dp_dyn[0] == -1;
	};

	int lo = 1, hi = n >> 1;
	while (lo != hi) {
		int mid = (lo + hi) >> 1;
		valid(mid) ? hi = mid : lo = mid + 1;
	}
	cout << lo;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 972 KB Output is correct
2 Correct 17 ms 1904 KB Output is correct
3 Correct 21 ms 2320 KB Output is correct
4 Correct 19 ms 2328 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3896 KB Output is correct
2 Correct 55 ms 5276 KB Output is correct
3 Correct 87 ms 5700 KB Output is correct
4 Correct 76 ms 5572 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 7112 KB Output is correct
2 Correct 110 ms 7280 KB Output is correct
3 Correct 99 ms 6980 KB Output is correct
4 Correct 142 ms 8008 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 13880 KB Output is correct
2 Correct 398 ms 16456 KB Output is correct
3 Correct 568 ms 17116 KB Output is correct
4 Correct 560 ms 20936 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 20524 KB Output is correct
2 Correct 563 ms 25872 KB Output is correct
3 Correct 653 ms 25068 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 20344 KB Output is correct
2 Correct 569 ms 25796 KB Output is correct
3 Correct 701 ms 24920 KB Output is correct
4 Correct 388 ms 26800 KB Output is correct