This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()
using i64 = long long;
void main_() {
int N, T, M;
cin >> N >> T >> M;
--T, --M;
if (T == M) {
cout << 0 << endl;
return;
}
vector<int> A(N - 1), B(N - 1);
vector<vector<int>> Tree(N);
rep(i, 0, N - 1) {
cin >> A[i] >> B[i];
Tree[--A[i]].push_back(--B[i]);
Tree[B[i]].push_back(A[i]);
}
vector<bool> isPath(N);
vector<int> path;
auto dfs = [&](auto &&self, const int v, const int p) -> bool {
bool ret = false;
for (const int t : Tree[v]) {
if (t == p) continue;
ret |= self(self, t, v);
}
if (v == T) ret = true;
isPath[v] = ret;
if (ret) path.push_back(v);
return ret;
};
dfs(dfs, M, -1);
reverse(ALL(path));
vector<int> dp(N);
auto dfs2 = [&](auto &&self, const int v, const int p) -> int {
vector<int> vals;
for (const int t : Tree[v]) {
if (t == p) continue;
if (isPath[t]) continue;
vals.push_back(self(self, t, v));
}
sort(ALL(vals), greater());
int cost = -1;
if (vals.empty()) cost = 0;
else if (vals.size() == 1) cost = 1;
else cost = vals[1] + (int)(vals.size()) - 1;
dp[v] = cost;
return dp[v] + 1;
};
for (const auto e : path) {
if (e == T) continue;
dfs2(dfs2, e, -1);
}
i64 ans = 1ll << 60;
int S = (int)path.size();
vector<int> rs(S);
per(i, 1, S) {
rs[i - 1] = rs[i] + (int)Tree[path[i - 1]].size() - 2;
}
vector<vector<int>> cList(S);
rep(i, 0, S - 1) {
vector<int> vals;
for (const int t : Tree[path[i]]) {
if (isPath[t]) continue;
vals.push_back(dp[t]);
}
sort(ALL(vals), greater());
rep(j, 0, (int)vals.size()) cList[i].push_back(vals[j] + (int)vals.size() - j);
}
int ok = 1 << 30, ng = -1;
while (ok - ng > 1) {
const auto m = (ok + ng) / 2;
int cnt1 = 0;
bool isOk = true;
rep(i, 0, S - 1) {
int baseCost = rs[i + 1];
int lm1 = -1, lm2 = -1;
rep(j, 0, (int)cList[i].size()) {
if (lm1 == -1 and cnt1 + j + cList[i][j] + baseCost <= m) {
lm1 = j;
}
if (lm2 == -1 and cnt1 + j + cList[i][j] + 2 + baseCost <= m) {
lm2 = j;
}
}
if (lm1 == -1 and cnt1 + cList[i].size() + baseCost <= m) lm1 = cList[i].size();
if (lm2 != -1 and cnt1 + lm2 + 1 <= i + 1) {
break;
}
if (lm1 == -1) {
isOk = false;
break;
}
cnt1 += lm1;
if (cnt1 > i + 1) {
isOk = false;
break;
}
}
(isOk ? ok : ng) = m;
}
cout << ok << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
main_();
}
Compilation message (stderr)
mousetrap.cpp: In function 'void main_()':
mousetrap.cpp:101:65: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
101 | if (lm1 == -1 and cnt1 + cList[i].size() + baseCost <= m) lm1 = cList[i].size();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mousetrap.cpp:65:9: warning: unused variable 'ans' [-Wunused-variable]
65 | i64 ans = 1ll << 60;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |