#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
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;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
26456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
258 ms |
73276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
26456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
26456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
