Submission #846670

#	Time	Username	Problem	Language	Result	Execution time	Memory
846670		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	324 ms	23796 KiB

torrent

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;

#define eb emplace_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()

int n, a, b;
vector<int> adj[N];
vector<pii> path;
int par[N];

void get(int u, int p) {
    for(int v : adj[u]) {
        if(v == p) continue;

        par[v] = u;
        get(v, u);
    }
}

int DFS(int u, int p, pii block) {
    int sum = 0;
    vector<int> res;

    for(int v : adj[u]) {
        if(v == p)
            continue;

        if(make_pair(u, v) == block or make_pair(v, u) == block)
            continue;

        res.eb(DFS(v, u, block));
    }

    sort(all(res));
    reverse(all(res));

    for(int i = 0; i < sz(res); i++)
        sum = max(sum, res[i] + (i + 1));

    return sum;
}

void process() {
    get(a, 0);
    int x = b;

    while(x != a) {
        path.eb(par[x], x);
        x = par[x];
    }

    reverse(all(path));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> a >> b;

    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].eb(v);
        adj[v].eb(u);
    }

    process();
    int l = 0, r = sz(path) - 1;

    while(r - l > 1) {
        int m = l + r >> 1;
        int x = DFS(a, 0, path[m]);
        int y = DFS(b, 0, path[m]);

        if(x < y) {
            l = m;

        } else r = m;
    }

    int ans = max(DFS(a, 0, path[l]), DFS(b, 0, path[l]));
    ans = min(ans, max(DFS(a, 0, path[r]), DFS(b, 0, path[r])));
    cout << ans;
}

Compilation message (stderr)

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

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