제출 #898501

#제출 시각아이디문제언어결과실행 시간메모리
898501AlcabelTorrent (COI16_torrent)C++17
100 / 100
194 ms64720 KiB
#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<int> maxR(k), maxL(k); int left = -1, right = n - 2; while (right - left > 1) { int mid = left + (right - left) / 2; maxR[0] = mid; for (int i = 0; i < k - 2; ++i) { int v = path[i]; maxR[i + 1] = -inf; 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) int maxx = maxR[i] - ((int)g[v].size() + 1 - j); if (j < (int)g[v].size()) { maxx = min(maxx, dp[g[v][j]]); } int 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] = max(-inf, maxx); break; } } } maxL[k - 1] = mid; for (int i = k - 1; i > 1; --i) { int v = path[i]; maxL[i - 1] = -inf; 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) int maxx = maxL[i] - ((int)g[v].size() + 1 - j); if (j < (int)g[v].size()) { maxx = min(maxx, dp[g[v][j]]); } int 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] = max(-inf, maxx); break; } } } bool 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...