Submission #246506

#	Time	Username	Problem	Language	Result	Execution time	Memory
246506		vanic	Torrent (COI16_torrent)	C++14	100 / 100	729 ms	29172 KiB

torrent

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

using namespace std;

const int maxn=3e5+5;

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

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]){
		return 0;
	}
	int sz=0;
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i]!=prosl && !bio[ms[x][i]]){
			sz++;
			svi.push_back(siri(ms[x][i], x));
		}
	}
	sort(svi.end()-sz, svi.end());
	val[x]=1;
	int br=1;
	while(br<=sz){
		if(val[x]<svi.back()+br){
			val[x]=svi.back()+br;
			jednako[x]=svi.back()-1;
		}
		else if(val[x]==svi.back()+br){
			jednako[x]=svi.back()-1;
		}
		br++;
		svi.pop_back();
	}
//	cout << "sirim " << x << " " << val[x] << " " << svi.size() << endl;;
	return val[x];
}

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

int binary2(int usp){
	int lo=0, hi=put.size()-2;
	int mid;
//	printf("krecem %d\n", usp);
	while(lo<hi){
		mid=(lo+hi)/2;
		bio[put[mid]]=1;
//		printf("%d %d\n", mid, siri(put[put.size()-2], b));
		if(siri(put[put.size()-2], b)>usp){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
		bio[put[mid]]=0;
	}
	return lo;
}

int ternary(int lo, int hi){
	int mid;
	int val1, val2;
	int val3, val4;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		bio[put[mid]]=1;
		val1=siri(put[1], a);
		bio[put[mid]]=0;
		bio[put[mid-1]]=1;
		val2=siri(put[put.size()-2], b);
		bio[put[mid-1]]=0;
//		printf("%d %d %d %d %d\n", mid, val1, val2, val3, val4);
		if(val1>val2){
			hi=mid-1;
		}
		else{
			lo=mid;
		}
	}
	bio[put[lo]]=1;
	val1=siri(put[1], a);
	val4=siri(put[put.size()-2], b);
	bio[put[lo]]=0;
	bio[put[lo-1]]=1;
	val2=siri(put[put.size()-2], b);
	bio[put[lo-1]]=0;
	bio[put[lo+1]]=1;
	val3=siri(put[1], a);
	bio[put[lo+1]]=0;
	return max(max(val[a], val[b]), min(max(val1, val2), max(val3, val4))); //nisam siguran za max(val[a], val[b]), al mislim da je ok
}

int main(){
	scanf("%d%d%d", &n, &a, &b);
	a--;
	b--;
	int c, d;
	for(int i=0; i<n-1; i++){
		scanf("%d%d", &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(val[a]);
//	return 0;
	hi=binary2(val[b]);
	int pri1, pri2;
	int pos1=binary1(jednako[a])-1, pos2=binary2(jednako[b])+1;
	bio[put[pos1]]=1;
	pri1=max(val[a]-1, max(val[b], siri(put[put.size()-2], b)));
	bio[put[pos1]]=0;
	bio[put[pos2]]=1;
	pri2=max(val[b]-1, max(val[a], siri(put[1], a)));
	bio[put[pos2]]=0;
	if(pos1+1>=pos2){
		pri2=max(val[a]-1, val[b]-1);
	}
//	printf("%d %d\n", lo, hi);
//	printf("%d %d\n", val[a], val[b]);
//	printf("%d %d\n", pos1, pos2);
//	printf("%d %d\n", jednako[a], jednako[b]);
	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));
		}*/
		if(put.size()==2){
			sol=max(val[a]-1, val[b]-1);
		}
		else{
			sol=min(min(pri1, pri2),  max(val[a], val[b]));
		}
	}
	else{
		sol=min(min(pri1, pri2), ternary(lo, hi+1));
	}
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'bool dfs(int, int)':
torrent.cpp:25: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:41: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 main()':
torrent.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~

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