Submission #1361956

#TimeUsernameProblemLanguageResultExecution timeMemory
1361956OwstinTorrent (COI16_torrent)C++20
0 / 100
165 ms22460 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define all(x) begin(x), end(x)
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n, a, b; cin >> n >> a >> b; a--; b--;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; u--; v--;
        adj[u].pb(v); adj[v].pb(u);
    }
    vector<int> prev(n);
    auto find = [&] (auto &&self, int node, int parent) -> void {
        for (auto x : adj[node]) {
            if (x == parent) {
                continue;
            }
            prev[x] = node;
            self(self, x, node);
        }
    };
    find(find, a, -1);
    int ind = b;
    vector<int> path;
    while (ind != a) {
        path.pb(ind);
        ind = prev[ind];
    }
    path.pb(a);
    reverse(all(path));
    vector<int> dp(n);
    auto dfs = [&] (auto &&self, int node, int parent, int cut, int d) -> void {
        vector<int> dist;
        dp[node] = d;
        for (auto x : adj[node]) {
            if (x == parent || node == path[cut] && x == path[cut + 1] || node == path[cut + 1] && x == path[cut]) {
                continue;
            }
            self(self, x, node, cut, d + 1);
            dist.pb(dp[x]);
        }
        sort(all(dist), greater<>());
        for (int i = 0; i < dist.size(); i++) {
            dp[node] = max(dp[node], dist[i] + i);
        }
    };
    int lo = 0; int hi = path.size() - 2;
    while (lo < hi) {
        dp.clear(); dp.resize(n);
        int mid = (lo + hi + 1) / 2;
        dfs(dfs, a, -1, mid, 0);
        dfs(dfs, b, -1, mid, 0);
        if (dp[a] <= dp[b]) {
            lo = mid;
        }
        else {
            hi = mid - 1;
        }
    }
    dp.clear(); dp.resize(n);
    dfs(dfs, a, -1, lo, 0);
    dfs(dfs, b, -1, lo, 0);
    cout << max(dp[a], dp[b]);
}

int main() {
    FAST_IO;
    //freopen("berries.in", "r", stdin);
    //freopen("berries.out", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...