Submission #1158978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158978		nh0902	Torrent (COI16_torrent)	C++20	0 / 100	2096 ms	20088 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 3e5 + 10;

const int M = 1e4;

const long long inf = 1e17;

int n;

vector<int> g[N];

int x, y;

int m, path[N]; // path from x to y

bool dfs(int u, int p, int d) {
    if (u == y) {
        path[d] = y;
        m = d;
        return true;
    }

    for (int v : g[u]) if (v != p) {
        if (dfs(v, u, d + 1)) {
            path[d] = u;
            return true;
        }
    }
    
    return false;
}

int dp[N];

void DFS(int u, int p, int b) {

    int max_child = 0;
    for (int v : g[u]) if (v != p && v != b) {
        DFS(v, u, b);
        max_child = max(max_child, dp[v]);
    }

    int cnt = 0;
    for (int v : g[u]) if (v != p && v != b) {
        if (dp[v] == max_child) cnt ++;
    }

    //cout << u << " " << max_child << " " << cnt << "\n";

    dp[u] = max_child + cnt;
}

int solve(int i) {
    memset(dp, 0, sizeof dp);
    DFS(x, x, path[i + 1]);
    DFS(y, y, path[i]);
    return max(dp[x], dp[y]);
}

int tenary_search() {
    int a = 1;
    int b = m - 1;
    while (a + 1 < b) {
        int mid1 = (2 * a + b) / 3;
        int mid2 = (a + 2 * b) / 3;
        int s1 = solve(mid1);
        int s2 = solve(mid2);
        if (s1 <= s2) b = mid2;
        else a = mid1;
    }

    int s1 = solve(a);
    int s2 = solve(b);

    return min(s1, s2);
}

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

    cin >> n >> x >> y;

    int u, v;

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

    dfs(x, x, 1);

    //cout << solve(1);

    cout << tenary_search();
    
    return 0;
}

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