oj.uz

Submission #118364

# Submission time Handle Problem Language Result Execution time Memory
118364 2019-06-18T19:06:20 Z teomrn Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 359 ms 63000 KB 
#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 {
		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++;
				}
			}

			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

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 23 ms 23808 KB Output is correct
6 Correct 22 ms 23808 KB Output is correct
7 Correct 22 ms 23808 KB Output is correct
8 Correct 23 ms 23808 KB Output is correct
9 Incorrect 22 ms 23808 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 359 ms 63000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 23 ms 23808 KB Output is correct
6 Correct 22 ms 23808 KB Output is correct
7 Correct 22 ms 23808 KB Output is correct
8 Correct 23 ms 23808 KB Output is correct
9 Incorrect 22 ms 23808 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 23 ms 23808 KB Output is correct
6 Correct 22 ms 23808 KB Output is correct
7 Correct 22 ms 23808 KB Output is correct
8 Correct 23 ms 23808 KB Output is correct
9 Incorrect 22 ms 23808 KB Output isn't correct
10 Halted 0 ms 0 KB -