//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int MAX_N = 1000002;
const int INF = 1e9;
int n, root, mouse_vertice, f[MAX_N], par[MAX_N];
bool on_path[MAX_N];
vector<int> p, g[MAX_N];
void enter() {
cin >> n >> root >> mouse_vertice;
for (int i=1; i<n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
}
void fix_root(int u) {
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i];
if (v!=par[u]) {
par[v] = u;
fix_root(v);
}
}
}
bool find_path(int u, int fn) {
if (u==fn)
return on_path[u] = true;
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i];
if (v!=par[u] && find_path(v, fn))
return on_path[u] = true;
}
return false;
}
int dp(int u) {
int m1 = 0, m2 = 0;
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i];
if (v!=par[u]) {
int tmp = dp(v);
if (tmp>=m1) {
m2 = m1;
m1 = tmp;
}
else {
m2 = max(m2, tmp);
}
}
}
return f[u] = g[u].size() - 1 + m2;
}
void init_tree() {
fix_root(root);
find_path(root, mouse_vertice);
dp(root);
}
bool check(int x) {
int used = 0, remain = 0;
int cur = mouse_vertice;
int sum_deg = 0;
for (int i=1; i<=n; ++i)
if (i!=root && on_path[i])
sum_deg += (g[i].size() - 2);
while (cur!=root) {
sum_deg -= (g[cur].size() - 2);
++remain;
p.clear();
for (int i=0; i<g[cur].size(); ++i) {
int u = g[cur][i];
p.push_back(f[u]);
}
sort(p.begin(), p.end(), greater<int>());
if (p.size()>remain &&
p[remain] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used > x) {
//debug(used);
return false;
}
int tmp = 0;
for (int i=0; i<p.size(); ++i) {
if (p[i] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used > x) {
--remain;
++tmp;
}
}
used += tmp;
cur = par[cur];
}
return true;
}
int bisect() {
int l = 0, r = INF, mid = (l + r) / 2;
while (l!=mid && mid!=r) {
if (check(mid))
r = mid;
else
l = mid;
mid = (l + r) / 2;
}
for (int i=l; i<=r; ++i)
if (check(i))
return i;
assert(0);
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
enter();
init_tree();
//PR(f, n);
//debug(check(4));
cout << bisect();
}
Compilation message
mousetrap.cpp: In function 'void fix_root(int)':
mousetrap.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
mousetrap.cpp: In function 'bool find_path(int, int)':
mousetrap.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
mousetrap.cpp: In function 'int dp(int)':
mousetrap.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
mousetrap.cpp: In function 'bool check(int)':
mousetrap.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[cur].size(); ++i) {
~^~~~~~~~~~~~~~
mousetrap.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (p.size()>remain &&
~~~~~~~~^~~~~~~
mousetrap.cpp:91:74: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
p[remain] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used > x) {
mousetrap.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<p.size(); ++i) {
~^~~~~~~~~
mousetrap.cpp:97:73: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (p[i] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used > x) {
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
656 ms |
76500 KB |
Output is correct |
| 2 |
Correct |
550 ms |
84708 KB |
Output is correct |
| 3 |
Correct |
1247 ms |
102872 KB |
Output is correct |
| 4 |
Correct |
605 ms |
102872 KB |
Output is correct |
| 5 |
Correct |
1563 ms |
122616 KB |
Output is correct |
| 6 |
Correct |
1467 ms |
136040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
