Submission #1355443

#TimeUsernameProblemLanguageResultExecution timeMemory
1355443i_love_springTorrent (COI16_torrent)C++20
69 / 100
185 ms45272 KiB
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
#define int long long 
const int inf = 2e9;

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    --a, --b;
    vector<vector<int>> g(n);
    for (int i = 1; i < n;i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }


    vector<int> dpA(n, 0), parA(n, -1);
    
    function<void(int, int)> dfsA = [&](int u, int p) {
        vector<int> arr;
        for (int v : g[u]) {
            if (v == p)
                continue;
            dfsA(v, u);
            parA[v] = u;
            if (v != b) 
                arr.push_back(dpA[v]);
        }

        sort(arr.rbegin(), arr.rend());
        for (int i = 0; i < arr.size(); i++)
            dpA[u] = max(dpA[u], i + 1 + arr[i]);

    };

    dfsA(a, -1);
    

    vector<int> dpB(n, 0), parB(n, -1);
    
    function<void(int, int)> dfsB = [&](int u, int p) {
        vector<int> arr;
        for (int v : g[u]) {
            if (v == p)
                continue;
            dfsB(v, u);
            parB[v] = u;
            if (v != a) 
                arr.push_back(dpB[v]);
        }

        sort(arr.rbegin(), arr.rend());
        for (int i = 0; i < arr.size(); i++)
            dpB[u] = max(dpB[u], i + 1 + arr[i]);

    };

    dfsB(b, -1);

    vector<int> path;
    int cur = parB[a];
    while (cur != b) 
        path.push_back(cur), cur = parB[cur];
    
    reverse(path.begin(), path.end());

    auto f = [&](int x) {
        if (x >= path.size() | x < 0)
            return inf;
        auto tmpA = dpA;
        auto tmpB = dpB;
        x = path[x];
        int z = parA[x];
        while (z != -1) {
            vector<int> arr;
            for (int v : g[z]) {
                if (v == parA[z] || v == x) 
                    continue;
                arr.push_back(dpA[v]);
            }
            
            dpA[z] = 0;
            sort(arr.rbegin(), arr.rend());
            for (int i = 1; i <= arr.size(); i++)
                dpA[z] = max(dpA[z], i + arr[i - 1]);
            z = parA[z];
        }

        z = x;
        while (z != -1) {
            vector<int> arr;
            for (int v : g[z]) {
                if (v == parB[z] || v == parA[x]) 
                    continue;
                arr.push_back(dpB[v]);
            }


            dpB[z] = 0;
            sort(arr.rbegin(), arr.rend());
            for (int i = 1; i <= arr.size(); i++)
                dpB[z] = max(dpB[z], i + arr[i - 1]);
            z = parB[z];
        }
        int res = max(dpA[a], dpB[b]);
        dpA = tmpA;
        dpB = tmpB;
        return res;
    };    

    int ans = max(dpA[a], dpB[b]);
    // for (int i = 0; i < path.size();i++)
    //     ans = min(ans, f(i));
    int l = 0, r = path.size() - 1;
    while (l < r) {
        int m = (l + r) / 2;
        int x1 = f(m);
        int x2 = f(m + 1);
        ans = min({ans, x1, x2});
        if (x1 >= x2)
            l = m + 1;
        else 
            r = m;
    }

    ans = min({ans, f(l), f(r)});

    cout << ans << "\n";
}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...