#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 1e6 + 5;
const int mod = 1e6 + 3;
const int inf = 1e9 + 1;
vector<int> g[NM];
int n, t, m, w[NM], W[NM], dep[NM], par[NM];
vector<pair<int, int>> L;
void dfs(int u = t, int p = 0)
{
if (u != t)
W[u] = W[par[u]] + max(0, (int)g[u].size() - 2);
int be = 0, sb = 0;
for (auto v : g[u])
{
if (v == p)
continue;
dep[v] = dep[u] + 1;
par[v] = u;
dfs(v, u);
if (be < w[v])
{
sb = be;
be = w[v];
}
else if (sb < w[v])
sb = w[v];
}
if (g[u].size() - !!p == 0)
w[u] = 0;
else if (g[u].size() - !!p == 1)
w[u] = 1;
else
w[u] += sb + g[u].size() - !!p;
}
bool check(int x)
{
int B = 0;
for (auto p : L)
if (p.se + B > x)
{
if (B > p.fi)
return false;
B++;
}
return true;
}
signed main()
{
if (fopen("in.txt", "r")) {
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
fastIO
cin >> n >> t >> m;
for (int i = 2; i <= n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs();
int u = m, prv = 0;
while (u != t)
{
for (auto v : g[u])
if (v != prv)
L.emplace_back(dep[m] - dep[u], w[v] + W[v] + 1);
prv = u;
u = par[u];
}
sort(L.begin(), L.end());
int l = -1, r = 2 * n;
while (l < r - 1)
{
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid;
}
cout << r;
}
Compilation message
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:97:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
97 | int mid = l + r >> 1;
| ~~^~~
mousetrap.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | freopen("in.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | freopen("out.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
84124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
