Submission #744317

#	Time	Username	Problem	Language	Result	Execution time	Memory
744317		nvujica	Torrent (COI16_torrent)	C++14	100 / 100	424 ms	27036 KiB

torrent

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 3e5 + 10;

int n, a, b, ans = maxn;
vector <int> v[maxn];
int par[maxn];
vector <int> t;

void rek(int x){
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == par[x]) continue;
		
		par[x2] = x;
		rek(x2);
	}
}

int rek2(int x, int p){
	vector <int> d;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == p) continue;
		
		d.push_back(rek2(x2, x));
	}
	
	sort(d.begin(), d.end());
	reverse(d.begin(), d.end());
	
	int maxi = 0;
	
	for(int i = 0; i < d.size(); i++){
		maxi = max(maxi, d[i] + i);
	}
	
	return maxi + 1;
}

int calc(int k){
	if(k < 0) return maxn;
	
	int poz;
	for(int i = 0; i < v[t[k]].size(); i++){
		if(v[t[k]][i] == t[k + 1]) poz = i;
	}
	v[t[k]].erase(v[t[k]].begin() + poz);
	
	for(int i = 0; i < v[t[k + 1]].size(); i++){
		if(v[t[k + 1]][i] == t[k]) poz = i;
	}
	v[t[k + 1]].erase(v[t[k + 1]].begin() + poz);
	
	int ra = rek2(a, 0);
	int rb = rek2(b, 0);
	
	ans = min(ans, max(ra, rb));
	
	v[t[k]].push_back(t[k + 1]);
	v[t[k + 1]].push_back(t[k]);
	
	return rb - ra;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> a >> b;
	
	for(int i = 0; i < n - 1; i++){
		int x, y;
		cin >> x >> y;
		
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	rek(a);
	
	int x = b;
	while(x != a){
		t.push_back(x);
		x = par[x];
	}
	t.push_back(a);
	
	int m = t.size();
	
	int lo = 0, hi = m - 2;
	while(lo < hi){
		int mid = (lo + hi) / 2;
		
		if(calc(mid) < 0) lo = mid + 1;
		else hi = mid;
	}
	
	calc(hi);
	calc(hi - 1);
	
	cout << ans - 1;
	
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void rek(int)':
torrent.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
torrent.cpp: In function 'int rek2(int, int)':
torrent.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
torrent.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < d.size(); i++){
      |                 ~~^~~~~~~~~~
torrent.cpp: In function 'int calc(int)':
torrent.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < v[t[k]].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
torrent.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < v[t[k + 1]].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~

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