Submission #367404

#	Time	Username	Problem	Language	Result	Execution time	Memory
367404		dolphingarlic	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1052 ms	169688 KiB

mousetrap

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, t, m, c;
vector<int> graph[1000001], chain;
ll dp[1000001], pref[1000001];
bool in_chain[1000001];

bool dfs(int node = t, int parent = 0) {
	ll mx1 = 0, mx2 = 0;
	for (int i : graph[node]) if (i != parent) {
		in_chain[node] |= dfs(i, node);
		if (dp[i] >= mx1) mx2 = mx1, mx1 = dp[i];
		else if (dp[i] > mx2) mx2 = dp[i];
	}
	sort(graph[node].begin(), graph[node].end(), [](int A, int B) { return dp[A] > dp[B]; });
	dp[node] = graph[node].size() - 1 + mx2;
	if (in_chain[node]) chain.push_back(node);
	return in_chain[node];
}

bool check(int mn) {
	int rem = 1, used = 0;
	for (int i = c - 1; i; i--, rem++) {
		int allowed = mn - pref[i] - used;
		for (int j : graph[chain[i]]) if (!in_chain[j]) {
			if (dp[j] <= allowed) break;
			if (!rem) return false;
			rem--, used++;
		}
	}
	return true;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> t >> m;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	in_chain[m] = true;
	dfs();
	reverse(chain.begin(), chain.end());
	c = chain.size();
	for (int i = 1; i < c; i++)
		pref[i] = pref[i - 1] + graph[chain[i]].size() - 2 + (i == c - 1);

	int l = pref[c - 1], r = n - 1;
	while (l != r) {
		int mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l;
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35