Submission #246326

#	Time	Username	Problem	Language	Result	Execution time	Memory
246326		vanic	Torrent (COI16_torrent)	C++14	0 / 100	1451 ms	22520 KiB

torrent

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <bitset>
#include <vector>

using namespace std;

const int maxn=3e5+5;

int n, a, b;
vector < int > ms[maxn];
vector < int > put;
int val[maxn];
bitset < maxn > bio;

bool dfs(int x, int prosl){
	put.push_back(x);
	if(x==b){
		return 1;
	}
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			if(dfs(ms[x][i], x)){
				return 1;
			}
		}
	}
	put.pop_back();
	return 0;
}

int siri(int x, int prosl){
	if(bio[x]){
//		cout << "NE" << endl;
		return 0;
	}
	vector < int > svi;
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i]!=prosl && !bio[ms[x][i]]){
			svi.push_back(siri(ms[x][i], x));
		}
	}
	if(svi.empty()){
		val[x]=1;
		return 1;
	}
	sort(svi.begin(), svi.end());
	val[x]=0;
	for(int i=0; i<svi.size(); i++){
		val[x]=max(val[x], svi[i]+(int)svi.size()-i);
	}
//	cout << "sirim " << x << " " << val[x] << " " << svi.size() << endl;;
	return val[x];
}

int binary1(){
	int lo=1, hi=put.size()-1;
	int mid;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		bio[mid]=1;
		if(siri(put[1], a)>val[a]){
			hi=mid-1;
		}
		else{
			lo=mid;
		}
		bio[mid]=0;
	}
	return lo;
}

int binary2(){
	int lo=0, hi=put.size()-2;
	int mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		bio[mid]=1;
		if(siri(put[put.size()-2], b)>val[b]){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
		bio[mid]=0;
	}
	return lo;
}

int ternary(int lo, int hi){
	int mid;
	int val1, val2;
	int val3, val4;
//	cout << put[1] << " " << put[put.size()-2] << '\n';
	while(lo<hi){
		mid=(lo+hi)/2+1;
		bio[put[mid]]=1;
//		cout << "poc" << endl;
		val1=siri(put[1], a);
		bio[put[mid]]=0;
		bio[put[mid-1]]=1;
//		cout << "poc" << endl;
		val2=siri(put[put.size()-2], b);
//		cout << "poc" << endl;
		val3=siri(put[1], a);
		bio[put[mid-1]]=0;
		bio[put[mid-2]]=1;
//		cout << "poc" << endl;
		val4=siri(put[put.size()-2], b);
		bio[put[mid-2]]=0;
//		cout << mid << endl;
//		cout << val1 << " " << val2 << " " << val3 << " " << val4 << '\n';
		if(max(val1, val2)>max(val3, val4)){
			hi=mid-1;
		}
		else{
			lo=mid;
		}
	}
	int sol=min(max(val1, val2), max(val3, val4));
	if(lo==1){
		sol=max(sol, max(val[a]-1, val[b]));
	}
	else if(lo==put.size()-1){
		sol=max(sol, max(val[a], val[b]-1));
	}
	else{
		sol=max(sol, max(val[a], val[b]));
	}
	return min(max(val1, val2), max(val3, val4));
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> a >> b;
	a--;
	b--;
	int c, d;
	for(int i=0; i<n-1; i++){
		cin >> c >> d;
		c--;
		d--;
		ms[c].push_back(d);
		ms[d].push_back(c);
	}
	dfs(a, a);
	siri(a, put[1]);
	siri(b, put[put.size()-2]);
	int lo, hi;
	lo=binary1();
	hi=binary2();
	int sol=1e9;
	if(hi+1<=lo){
		if(hi==0){
			sol=min(sol, max(val[a]-1, val[b]));
		}
		if(lo==put.size()-1){
			sol=min(sol, max(val[a], val[b]-1));
		}
		sol=min(sol,  max(val[a], val[b]));
	}
	else{
		sol=ternary(lo, hi+1);
	}
	cout << sol << '\n';
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'bool dfs(int, int)':
torrent.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
torrent.cpp: In function 'int siri(int, int)':
torrent.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
torrent.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<svi.size(); i++){
               ~^~~~~~~~~~~
torrent.cpp: In function 'int ternary(int, int)':
torrent.cpp:126:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  else if(lo==put.size()-1){
          ~~^~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:162:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(lo==put.size()-1){
      ~~^~~~~~~~~~~~~~
torrent.cpp: In function 'int ternary(int, int)':
torrent.cpp:94:6: warning: 'val1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int val1, val2;
      ^~~~
torrent.cpp:94:12: warning: 'val2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int val1, val2;
            ^~~~
torrent.cpp:95:6: warning: 'val3' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int val3, val4;
      ^~~~
torrent.cpp:95:12: warning: 'val4' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int val3, val4;
            ^~~~

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