1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m, k;
	std::cin >> n >> m >> k;
	if (k == n) {
		std::cout << '0';
		return 0;
	}
	std::vector<std::vector<int>> graph(n);
	for (int i = 0; i < m; i++) {
		int x, y;
		std::cin >> x >> y;
		graph[x - 1].push_back(y - 1);
	}
	std::vector<int> longest_paths(n);
	std::vector<int> sources(n);
	std::function<int(int, std::vector<bool>&, std::vector<bool>)> f
		= [&](int left_to_remove, std::vector<bool>& removed, std::vector<bool> attempted) {
		int winner_index = 0;
		std::fill(longest_paths.begin(), longest_paths.end(), 1);
		std::fill(sources.begin(), sources.end(), -1);
		for (int i = 0; i < n; i++) {
			if (!removed[i]) {
				int longest = longest_paths[i];
				if (longest > longest_paths[winner_index])
					winner_index = i;
				for (const auto& edge : graph[i]) {
					int& edge_longest = longest_paths[edge];
					if (edge_longest <= longest) {
						edge_longest = longest + 1;
						sources[edge] = i;
					}
				}
			}
		}
		int path_length = longest_paths[winner_index];
		if (left_to_remove == 0)
			return path_length;
		left_to_remove--;
		std::vector<int> path(path_length);
		for (auto&& index : path) {
			index = winner_index;
			winner_index = sources[winner_index];
		}
		int path_middle = path_length / 2;
		int best_result = path_length;
		for (int i = 1; i <= best_result; i++) {
			int index = path_middle + (i & 1 ? i : -i) / 2;
			int min_new_max_length = std::max(index, path_length - 1 - index);
			if (min_new_max_length / (k + 1) >= best_result)
				return best_result;
			int attempt = path[index];
			if (!attempted[attempt]) {
				attempted[attempt] = true;
				removed[attempt] = true;
				int result = f(left_to_remove, removed, attempted);
				removed[attempt] = false;
				if (result < best_result)
					best_result = result;
			}
		}
		return best_result;
	};
	std::vector<bool> removed(n);
	std::vector<bool> attempted(n);
	std::cout << f(k, removed, attempted);
	return 0;
}