이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5, inf = 1e9;
vector<int> g[maxn];
vector<int> getPath(int v, int p, int t) {
if (v == t) {
return {v};
}
vector<int> res;
for (const int& u : g[v]) {
if (u != p) {
res = getPath(u, v, t);
if (!res.empty()) {
res.emplace_back(v);
return res;
}
}
}
return {};
}
char isOnPath[maxn];
int dp[maxn];
vector<int> prefMax[maxn], sufMax[maxn];
void dfsDp(int v, int p) {
dp[v] = 0;
for (int i = 0; i < (int)g[v].size(); ++i) {
int u = g[v][i];
if (u != p && !isOnPath[u]) {
dfsDp(u, v);
} else {
swap(g[v][i], g[v].back());
g[v].pop_back();
--i;
}
}
sort(g[v].begin(), g[v].end(), [&](const int& A, const int& B) {
return dp[A] < dp[B];
});
dp[v] = 0;
prefMax[v].resize(g[v].size() + 1);
prefMax[v][0] = -1;
for (int i = 0; i < (int)g[v].size(); ++i) {
int cur = dp[g[v][i]] + (int)g[v].size() - i;
prefMax[v][i + 1] = max(prefMax[v][i], cur);
dp[v] = max(dp[v], cur);
}
sufMax[v].resize(g[v].size() + 1);
sufMax[v].back() = -1;
for (int i = (int)g[v].size() - 1; i >= 0; --i) {
int cur = dp[g[v][i]] + (int)g[v].size() - i;
sufMax[v][i] = max(sufMax[v][i + 1], cur);
}
}
void solve() {
int n, a, b;
cin >> n >> a >> b;
--a, --b;
for (int i = 0; i < n - 1; ++i) {
int v, u;
cin >> v >> u;
--v, --u;
g[v].emplace_back(u);
g[u].emplace_back(v);
}
vector<int> path = getPath(a, -1, b);
for (const int& v : path) {
isOnPath[v] = true;
}
for (const int& v : path) {
dfsDp(v, -1);
}
int k = path.size();
vector<long long> maxR(k), maxL(k);
int left = -1, right = n - 2;
while (right - left > 1) {
int mid = left + (right - left) / 2;
maxR[0] = mid;
bool able = true;
for (int i = 0; i < k - 2; ++i) {
int v = path[i];
bool defined = false;
for (int j = g[v].size(); j >= 0; --j) {
// max(prefMax[v][j] + 1, sufMax[v][j], x + g[v].size() + 1 - j) <= maxR[i]
// x >= (j > 0 ? dp[g[v][j - 1]] : -inf)
long long maxx = maxR[i] - ((int)g[v].size() + 1 - j);
if (j < (int)g[v].size()) {
maxx = min(maxx, dp[g[v][j]] * 1ll);
}
long long minx = (j > 0 ? dp[g[v][j - 1]] : -inf);
if (max(prefMax[v][j] + 1, sufMax[v][j]) <= maxR[i] && minx <= maxx) {
maxR[i + 1] = maxx;
defined = true;
break;
}
}
if (!defined) {
able = false;
break;
}
}
maxL[k - 1] = mid;
for (int i = k - 1; i > 1; --i) {
int v = path[i];
bool defined = false;
for (int j = g[v].size(); j >= 0; --j) {
// max(prefMax[v][j] + 1, sufMax[v][j], x + g[v].size() + 1 - j) <= maxL[i]
// x >= (j > 0 ? dp[g[v][j - 1]] : -inf)
long long maxx = maxL[i] - ((int)g[v].size() + 1 - j);
if (j < (int)g[v].size()) {
maxx = min(maxx, dp[g[v][j]] * 1ll);
}
long long minx = (j > 0 ? dp[g[v][j - 1]] : -inf);
if (max(prefMax[v][j] + 1, sufMax[v][j]) <= maxL[i] && minx <= maxx) {
maxL[i - 1] = maxx;
defined = true;
break;
}
}
if (!defined) {
able = false;
break;
}
}
if (able) {
able = false;
for (int i = 0; i < k - 1; ++i) {
if (maxR[i] >= dp[path[i]] && maxL[i + 1] >= dp[path[i + 1]]) {
able = true;
break;
}
}
}
if (able) {
right = mid;
} else {
left = mid;
}
}
cout << right << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |