Submission #246414

#	Time	Username	Problem	Language	Result	Execution time	Memory
246414		vanic	Torrent (COI16_torrent)	C++14	0 / 100	1674 ms	46568 KiB

torrent

#include <iostream>
#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;

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;
	}
	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++){
		if(val[x]<svi[i]+(int)svi.size()-i){
			val[x]=svi[i]+(int)svi.size()-i;
			jednako[x]=svi[i]-1;
		}
	}
//	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[mid]=1;
		if(siri(put[1], a)>usp){
			hi=mid-1;
		}
		else{
			lo=mid;
		}
		bio[mid]=0;
	}
	return lo;
}

int binary2(int usp){
	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)>usp){
			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;
	int sol1=-1, vrij;
	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);
		val3=siri(put[1], a);
		bio[put[mid-1]]=0;
		bio[put[mid-2]]=1;
		val4=siri(put[put.size()-2], b);
		bio[put[mid-2]]=0;
		if(abs(val1-val2)>abs(val3-val4)){
			hi=mid-1;
		}
		else if(abs(val1-val2)<=abs(val3-val4)){
			lo=mid;
		}
/*		else{
			sol1=mid;
			vrij=max(val1, val2);
			break;
		}*/
	}
/*	int sol, sol2;
	if(sol1!=-1){
		cout << "usao"  << endl;
		sol=vrij;
		sol2=1e9;
		if(sol1-1==1){
			sol2=max(sol, max(val[a]-1, val[b]));
		}
		if(sol1==put.size()-1){
			sol=max(sol, max(val[a], val[b]-1));
		}
		else{
			sol=max(sol, max(val[a], val[b]));
		}
		sol=min(sol, sol2);
	}
	else{
		cout << "ovdje" << endl;
		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 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(){
	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(val[a]);
	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;
	int sol=1e9;
	assert(0);
	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));
	}
	cout << sol << '\n';
	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:52: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:100:6: warning: unused variable 'sol1' [-Wunused-variable]
  int sol1=-1, vrij;
      ^~~~
torrent.cpp:100:15: warning: unused variable 'vrij' [-Wunused-variable]
  int sol1=-1, vrij;
               ^~~~

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