Submission #984447

#	Time	Username	Problem	Language	Result	Execution time	Memory
984447		duckindog	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	258 ms	73276 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;
}

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());
	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 (int i = 0; i < best.size(); ++i) value.push_back({best[i], i + 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 true;
	};

	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:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i < best.size(); ++i) value.push_back({best[i], i + 1});
      |                   ~~^~~~~~~~~~~~~
mousetrap.cpp:57: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]
   57 |  for (int i = 0; i < value.size(); ++i) value[i].first += value.size() - i;
      |                  ~~^~~~~~~~~~~~~~
mousetrap.cpp:72:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |   int mid = l + r >> 1;
      |             ~~^~~

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