Submission #743650

#	Time	Username	Problem	Language	Result	Execution time	Memory
743650		Lukap	Torrent (COI16_torrent)	C++14	100 / 100	707 ms	33736 KiB

torrent

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5 + 7;

int a,b,n;
vector<int> susjedi[MAXN], path;
int cost[MAXN];
pair<int, int> obris;
vector<int> v[MAXN];

bool put (int x, int p, int y) {
    if (x == y) {
        path.push_back (x);
        return 1;
    }
    for (auto nx: susjedi[x]) {
        if (nx == p) continue;
        if (put (nx, x, y)) {
            path.push_back (x);
            return 1;
        }
    }
    return 0;
}

void dfs (int x, int p) {
    cost[x] = 0;
    for (auto nx: susjedi[x]) {
        if (nx == p) continue;
        if ((obris.first == x && obris.second == nx) || (obris.first == nx && obris.second == x)) continue;
        dfs (nx, x);
        v[x].push_back (cost[nx]);
    }
    sort (v[x].begin(), v[x].end ());
    int cnt = 1;
    for (int i = v[x].size () - 1; i >= 0; i--) {
        cost[x] = max (cost[x], v[x][i] + cnt);
        cnt++;
    }
}

void clean () {
    for (int i = 0; i < n; i++) v[i].clear ();
}

int solve (int k) {
    obris = {path[k], path[k + 1]};
    clean ();
    dfs (a, -1);
    dfs (b, -1);
    return max (cost[a], cost[b]);
}

int bs () {
    int lo = 0, hi = path.size() - 2;

    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        solve (mid);

        if (cost[a] == cost[b]) {
            lo = mid;
            break;
        }
        if (cost[b] < cost[a]) lo = mid;
        else hi = mid - 1;
    }

    int rj = solve (lo);

    lo = 0, hi = path.size() - 2;

    while (lo < hi) {
        int mid = (lo + hi) / 2;
        solve (mid);

        if (cost[a] == cost[b]) {
            lo = mid;
            break;
        }
        if (cost[b] < cost[a]) lo = mid + 1;
        else hi = mid;
    }

    rj = min (rj, solve (lo));

    return rj;
}

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

    cin >> n >> a >> b;
    a--;b--;

    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--;y--;
        susjedi[x].push_back (y);
        susjedi[y].push_back (x);
    }
    put (a, -1, b);

    cout << bs ();

    return 0;
}

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