Submission #1000059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000059		BF001	Torrent (COI16_torrent)	C++17	100 / 100	326 ms	30140 KiB

torrent

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

#define N 300005

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

void init(int u, int p){
	for (auto x : adj[u]){
		if (x == p) continue;
		par[x] = u;
		init(x, u);
	}
}

bool cmp(int& a, int& b){
	return a > b;
}

int dfs(int u, int p, int x, int y){
	vector<int> tmp;
	dp[u] = 0;
	for (auto v : adj[u]){
		if (v == p) continue;
		if (u == x && v == y) continue;
		if (u == y && v == x) continue;
		dfs(v, u, x, y);
		tmp.push_back(dp[v] + 1);
	}
	sort(tmp.begin(), tmp.end(), cmp);
	for (int i = 0; i < (int) tmp.size(); i++){
		dp[u] = max(dp[u], tmp[i] + i);
	}
	return dp[u];
}

bool check(int x){
	int y = par[x];
	return dfs(a, 0, x, y) > dfs(b, 0, x, y);
}

int cal(int x){
	int y = par[x];
	return max(dfs(a, 0, x, y), dfs(b, 0, x, y));
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
    cin >> n >> a >> b;
    for (int i = 1; i <= n - 1; i++){
    	int u, v;
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }

    init(a, 0);

    int u = b;
    vector<int> path;
    while (u != a){
    	path.push_back(u);
    	u = par[u];
	}

	int l = 0, r = path.size() - 1, res = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(path[mid])){
			l = mid + 1;
			res = mid;
		}
		else r = mid - 1;
	}

	if (res < path.size() - 1) res++;
	int ans = cal(path[res]);
	if (res > 1) ans = min(ans, cal(path[res - 2]));
	if (res  + 2 <= path.size() - 1) ans = min(ans, cal(path[res + 2]));
	if (res > 0) ans = min(ans, cal(path[res - 1]));
	if (res < r) ans = min(ans, cal(path[res + 1]));
	
	cout << ans;

    return 0;
}     

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:79:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  if (res < path.size() - 1) res++;
      |      ~~~~^~~~~~~~~~~~~~~~~
torrent.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  if (res  + 2 <= path.size() - 1) ans = min(ans, cal(path[res + 2]));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~

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