Submission #118365

#	Time	Username	Problem	Language	Result	Execution time	Memory
118365		teomrn	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1041 ms	151168 KiB

mousetrap

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

const int NMAX = 1000010;
vector <int> adia[NMAX];
int cost[NMAX];
int tata[NMAX];
int nr_op;

void dfs(int nod, int t)
{
	if (t)
		adia[nod].erase(find(adia[nod].begin(), adia[nod].end(), t));
	tata[nod] = t;

	for (auto i : adia[nod])
		dfs(i, nod);

	int max1 = 0, max2 = 0;
	for (auto i : adia[nod]) {
		if (cost[i] > max1)
			max2 = max1, max1 = cost[i];
		else if (cost[i] > max2)
			max2 = cost[i];
	}

	cost[nod] = adia[nod].size() + max2;
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	//ifstream cin("q.in");


	int n, root, x;
	cin >> n >> root >> x;

	if (root == x) {
		cout << "0\n";
		return 0;
	}

	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adia[a].push_back(b);
		adia[b].push_back(a);
	}

	dfs(root, 0);

	vector <int> stramosi, _sp;
	while (x != root) {
		stramosi.push_back(x);
		_sp.push_back(0);
		x = tata[x];
	}
	_sp.push_back(0);

	for (int i = stramosi.size() - 1; i >= 0; i--) {
		_sp[i] = adia[stramosi[i]].size() - (i != 0);
		_sp[i] += _sp[i + 1];
	}


	auto verif = [&](int x) -> bool {
		auto sp = _sp;

		int inert = 1, operatii = 0;
		for (int i = 0; i < stramosi.size(); i++) {
			int prv = (i ? stramosi[i - 1] : 0);

			for (auto fiu : adia[stramosi[i]]) {
				if (fiu == prv)
					continue;
				if (cost[fiu] + operatii + sp[i] >= x) {
					if (!inert)
						return 1;
					inert--;
					operatii++;
					sp[i]--;
				}
			}

			inert++;
		}
		return operatii >= x;
	};

	int ans = 0, ok = 1;
	for (int p = 1; p; p = (ok ? 2 * p : p / 2)) {
		if (verif(ans + p))
			ans += p;
		else
			ok = 0;
	}

	cout << ans << '\n';

	return 0;
}

Compilation message (stderr)

mousetrap.cpp: In lambda function:
mousetrap.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < stramosi.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~

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