Submission #1027601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027601		vjudge1	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	674 ms	214476 KiB

mousetrap

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1'000'000 + 10;
int n, t, m;
vector<int> ad[N];
vector<int> path;
bool inPath[N];
 
bool dfs1(int u, int p = -1) { 
	inPath[u] = u == t;
	for (const auto& v : ad[u]) { 
		if (v == p) continue;
		inPath[u] |= dfs1(v, u);
	}
	if (inPath[u]) path.push_back(u);
	return inPath[u];
}
int f[N];
void dfs2(int u, int p = -1) { 
	vector<int> best {0, 0};
	for (const auto& v : ad[u]) { 
		if (v == p || inPath[v]) continue;
		dfs2(v, u);
		best.push_back(f[v]);
	}
	sort(best.begin(), best.end(), greater<>());
	f[u] = best.size() + best[1] - 2;
	// cerr << u << " ";
  // for (const auto& x : best) cerr << x << " "; cerr << "\n";
}
 
int32_t 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;
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
 
	dfs1(m);
	
	vector<pair<int, int>> value;
	{
		reverse(path.begin(), path.end());
		path.pop_back();
		
		int it = 0;
		for (const auto& u : path) {
			vector<int> best;
			for (const auto& v : ad[u]) { 
				if (inPath[v]) continue;
				dfs2(v, u);
				best.push_back(f[v]);
			}
			sort(best.begin(), best.end(), greater<>());
			for (const auto& x : best) value.push_back({x, it + 1}); 
			it += 1;
		}
	}
	
	for (int i = 0; i < value.size(); ++i) value[i].first += value.size() - i;
 
	auto chk = [&](int mid) {
		int it = 0;
		for (const auto& [val, d] : value) { 
			if (it + val > mid) { 
				if (it >= d) return false;
				it += 1;
			}
		}
		return it <= mid;
	};
 
	int l = 0, r = n * 2, it = 0;
	while (l <= r) { 
		int mid = l + r >> 1;
		if (chk(mid)) r = (it = mid) - 1;
		else l = mid + 1;
	}
	cout << it << "\n";
} 

Compilation message (stderr)

mousetrap.cpp: In function 'int32_t main()':
mousetrap.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i = 0; i < value.size(); ++i) value[i].first += value.size() - i;
      |                  ~~^~~~~~~~~~~~~~
mousetrap.cpp:80:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   int mid = l + r >> 1;
      |             ~~^~~

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