Submission #891839

#	Time	Username	Problem	Language	Result	Execution time	Memory
891839		Beerus13	Torrent (COI16_torrent)	C++14	100 / 100	305 ms	30940 KiB

torrent

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

int n, a, b, par[ar];
vector<int> adj[ar];
int dp[ar];
int del, ans = 1e9;

void build_tree(int u, int p) {
    for(int v : adj[u]) if(v != p){
        par[v] = u;
        build_tree(v, u);
    }
}

void dfs(int u, int p) {
    dp[u] = 0;
    priority_queue<int> q;
    for(int v : adj[u]) if(v != p && v != del) {
        dfs(v, u);
        q.push(dp[v]);
    }
    int cnt = 1;
    while(q.size()) {
        dp[u] = max(dp[u], cnt + q.top());
        q.pop();
        ++cnt;
    }
}

bool check(int u, int v) {
    del = v;
    dfs(a, 0);
    del = u;
    dfs(b, 0);
    ans = min(ans, max(dp[a], dp[b]));
    return dp[u] > dp[v];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for(int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    build_tree(a, 0);
    if(a == b) {
        dfs(a, 0);
        return cout << dp[a], 0;
    }
    vector<int> road;
    int tmp = b; while(tmp != a) {
        road.push_back(tmp);
        tmp = par[tmp];
    }
    if(n <= 1000) {
        for(int x : road) check(par[x], x);
        return cout << ans, 0;
    }
    int l = 0, r = road.size() - 1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(par[road[mid]], road[mid])) l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;
}

Compilation message (stderr)

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

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