Submission #989500

#	Time	Username	Problem	Language	Result	Execution time	Memory
989500		LOLOLO	Torrent (COI16_torrent)	C++17	100 / 100	266 ms	34280 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 10;
vector <pair <int, int>> ed[N];
int par[N], in[N], ou[N], id[N], timer = 1;
int dp[N];

void dfs(int u, int v) {
    in[u] = ++timer;
    for (auto x : ed[u]) {
        if (x.f == v)
            continue;

        par[x.f] = u;
        id[x.f] = x.s;
        dfs(x.f, u);
    }

    ou[u] = timer;
}

bool is(int a, int b) {
    return in[a] <= in[b] && ou[a] >= ou[b];
}

vector <int> path(int a, int b) {
    vector <int> L;
    while (is(a, b) == 0) {
        L.pb(id[a]);
        a = par[a];
    }

    vector <int> R;
    while (a != b) {
        R.pb(id[b]);
        b = par[b];
    }

    reverse(all(R));
    for (auto x : R)
        L.pb(x);

    return L;    
}

void dq(int u, int v, int ban) {
    dp[u] = 0;
    vector <int> lst;
    for (auto x : ed[u]) {
        if (x.f == v || x.s == ban)
            continue;

        dq(x.f, u, ban);
        lst.pb(dp[x.f]);
    }

    sort(all(lst), greater <int> ());
    int c = 1;
    for (auto x : lst) {
        dp[u] = max(x + c, dp[u]);
        c++;
    }
}

int solve(int x, int ban) {
    dq(x, x, ban);
    return dp[x];
}

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

    int n, a, b;
    cin >> n >> a >> b;

    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        ed[x].pb({y, i});
        ed[y].pb({x, i});
    }

    dfs(1, 1);

    vector <int> road = path(a, b);
    int ans = 1e9, l = 0, r = sz(road) - 1, m;
    while (l <= r) {
        m = (l + r) / 2;
        int A = solve(a, road[m]), B = solve(b, road[m]);
        if (A <= B) {
            l = m + 1;
        } else {
            r = m - 1;
        }

        ans = min(ans, max(A, B));
    } 

    cout << ans << '\n';
    return 0;
} 

/*
6 2 1
1 2
2 3
2 4
1 5
5 6
*/

/*
10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10
*/ 

/*
17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2
*/

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