Submission #1213630

#TimeUsernameProblemLanguageResultExecution timeMemory
1213630iamhereforfunTorrent (COI16_torrent)C++20
100 / 100
231 ms26004 KiB
// IamHereForFun // #include <bits/stdc++.h> using namespace std; const int N = 3e5 + 5; const int M = 1e2 + 5; const int LG = 20; const int S = 1e5 + 5; const int P = 37; const int INF = 1e9 + 5; const int MOD = 1e9 + 7; int n, st1, st2, dp[N], res; vector<int> adj[N], path; bool dfs1(int c, int p) { if (c == st2) { path.push_back(c); return true; } for (int i : adj[c]) { if (i == p) continue; if (dfs1(i, c)) { path.push_back(c); return true; } } return false; } void dfs2(int c, int p, int id) { dp[c] = 0; vector<int> v; for (int i : adj[c]) { if (i == p) continue; if (i == path[id]) continue; dfs2(i, c, id); v.push_back(dp[i]); } sort(v.rbegin(), v.rend()); for (int x = 0; x < v.size(); x++) { v[x] += x + 1; dp[c] = max(dp[c], v[x]); } } void solve() { cin >> n >> st1 >> st2; if (st1 > st2) swap(st1, st2); for (int x = 0; x < n - 1; x++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs1(st1, 0); reverse(path.begin(), path.end()); // for(int i : path) cout << i << " "; // cout << "\n"; int l = 0, r = path.size() - 2, ans = 0; while (l <= r) { int m = (l + r) / 2; dfs2(st1, 0, m + 1); dfs2(st2, 0, m); // cout << "\n"; if (dp[st1] <= dp[st2]) { l = m + 1; ans = m; } else { r = m - 1; } } // cout << ans << "\n"; dfs2(st1, 0, ans + 1); dfs2(st2, 0, ans); // cout << "\n"; // for (int x = 1; x <= n; x++) // { // cout << dp[x] << " " << x << "\n"; // } res = max(dp[st1], dp[st2]); if (ans + 2 < path.size()) { dfs2(st1, 0, ans + 2); dfs2(st2, 0, ans + 1); res = min(res, max(dp[st1], dp[st2])); } cout << res; } signed main() { // freopen("CP.INP", "r", stdin); // freopen("CP.OUT", "w", stdout); // freopen("promote.in", "r", stdin); // freopen("promote.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; for (int x = 1; x <= t; x++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...