Submission #1115069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115069		Zero_OP	Torrent (COI16_torrent)	C++14	0 / 100	422 ms	30660 KiB

torrent

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    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].emplace_back(v);
        adj[v].emplace_back(u);
    }

    vector<int> depth(N), par(N);

    function<void(int, int)> dfs = [&](int u, int p){
        for(auto v : adj[u]) if(v != p){
            depth[v] = depth[u] + 1;
            par[v] = u;
            dfs(v, u);
        }
    };

    vector<int> dp(N);

    function<void(int, int, int)> dfs_calc = [&](int u, int p, int cut){
        dp[u] = 0;
        vector<int> dps;
        for(auto v : adj[u]) if(v != p && v != cut){
            dfs_calc(v, u, cut);
            dps.emplace_back(dp[v]);
        }

        sort(dps.begin(), dps.end(), greater<int>());
        for(int i = 0; i < (int)dps.size(); ++i){
            dp[u] = max(dp[u], dps[i] + i + 1);
        }
    };

    function<int(int, int)> f = [&](int rt, int cut){
        dfs_calc(rt, -1, cut);
        return dp[rt];
    };

    dfs(a, -1);

    int l = 0, r = depth[b] - 1, ans = 1e9, last_opt = b;
    while(l <= r){
        int mid = l + r >> 1;

        int cur = b;
        for(int i = 0; i < mid; ++i) cur = par[cur];

        int eval_a = f(a, cur), eval_b = f(b, par[cur]);
        ans = min(ans, max(eval_a, eval_b));

        if(eval_a >= eval_b) last_opt = cur, l = mid + 1; //last eval_a >= eval_b
        else r = mid - 1;
    }

    if(par[last_opt] != a){ //first eval_a < eval_b
        last_opt = par[last_opt];
        ans = min(ans, max(f(a, par[last_opt]), f(b, last_opt)));
    }

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid = l + r >> 1;
      |                   ~~^~~

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69