oj.uz

Submission #984449

# Submission time Handle Problem Language Result Execution time Memory
984449 2024-05-16T16:49:23 Z duckindog Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 281 ms 60120 KB 
#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;
	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

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

Subtask #1
0 / 20.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

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