oj.uz

Submission #1115072

# Submission time Handle Problem Language Result Execution time Memory
1115072 2024-11-20T01:53:02 Z Zero_OP Torrent (COI16_torrent) C++14
100 / 100
 368 ms 33100 KB 
#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 = max(f(a, b), f(b, par[b])), 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){
        last_opt = par[last_opt];
        ans = min(ans, max(f(a, last_opt), f(b, par[last_opt])));
    }

    cout << ans << '\n';

    return 0;
}

Compilation message

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

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 23368 KB Output is correct
2 Correct 302 ms 25364 KB Output is correct
3 Correct 303 ms 28488 KB Output is correct
4 Correct 368 ms 30668 KB Output is correct
5 Correct 278 ms 26952 KB Output is correct
6 Correct 275 ms 28052 KB Output is correct
7 Correct 311 ms 33100 KB Output is correct