Submission #757825

#TimeUsernameProblemLanguageResultExecution timeMemory
757825taherTorrent (COI16_torrent)C++17
100 / 100
460 ms30352 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "C:\GCC\debug.h" #else #define debug(...) void(42) #endif int main() { ios::sync_with_stdio(false); cin.tie(0); int n, a, b; cin >> n >> a >> b; --a, --b; vector<vector<array<int, 2>>> adj(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back({v, i}); adj[v].push_back({u, i}); } vector<int> dp(n); function<void(int, int, int)> Dfs = [&](int u, int prev, int blocked_edge) { dp[u] = 0; vector<int> children; for (auto v : adj[u]) { if (v[0] == prev || v[1] == blocked_edge) { continue; } Dfs(v[0], u, blocked_edge); children.push_back(dp[v[0]]); } sort(children.begin(), children.end()); for (int i = (int) children.size() - 1; i >= 0; i--) { int add = (int) children.size() - i; dp[u] = max(dp[u], children[i] + add); } return ; }; vector<int> edges; function<bool(int, int)> Root = [&](int u, int prev) { if (u == b) { return true; } bool found = false; for (auto v : adj[u]) { if (v[0] == prev) { continue; } if (Root(v[0], u)) { found = true; edges.push_back(v[1]); } } return found; }; Root(a, -1); int res = 12345678; reverse(edges.begin(), edges.end()); int low = 0, high = (int) edges.size() - 1; while (low <= high) { int mid = low + (high - low) / 2; Dfs(a, -1, edges[mid]); Dfs(b, -1, edges[mid]); if (dp[a] <= dp[b]) { low = mid + 1; } else { high = mid - 1; } } --low; if (low >= 0) { Dfs(a, -1, edges[low]); Dfs(b, -1, edges[low]); res = min(res, max(dp[a], dp[b])); } ++low; if (low < (int) edges.size()) { Dfs(a, -1, edges[low]); Dfs(b, -1, edges[low]); res = min(res, max(dp[a], dp[b])); } cout << res << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...