Submission #1137054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137054		Trisanu_Das	Torrent (COI16_torrent)	C++20	31 / 100	2094 ms	27460 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int INF = 1e18;

int n, a, b;
vector<int> del;
vector<vector<array<int, 2>>> g;
vector<int> path_edge_indices;

bool find_path_to_b(int u, int p) {
    if (u == b) return true;
    for (auto [v, ind] : g[u]) {
        if (v != p && !del[ind] && find_path_to_b(v, u)) {
            path_edge_indices.push_back(ind);
            return true;
        }
    }
    return false;
}

int calc_cost(int u, int p) {
    vector<int> costs;
    for (auto [v, ind] : g[u]) 
        if (v != p && !del[ind]) costs.push_back(calc_cost(v, u));
    sort(costs.rbegin(), costs.rend());
    int cost = 0;
    for (int i = 0; i < costs.size(); ++i) 
        cost = max(cost, i + 1 + costs[i]);
    return cost;
}

void solve() {
    cin >> n >> a >> b;
    a--, b--;
    g.resize(n), del.resize(n - 1);
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v, --u, --v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    if (a == b) {
        cout << calc_cost(a, -1) << '\n';
        return;
    }
    int ans = INF;
    find_path_to_b(a, -1);
    for (int ind : path_edge_indices) {
        del[ind] = true;
        ans = min(ans, max(calc_cost(a, -1), calc_cost(b, -1)));
        del[ind] = false;
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), solve();
}

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