답안 #101070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101070 2019-03-16T10:41:08 Z JedrzejOlkowski Torrent (COI16_torrent) C++14
0 / 100
757 ms 24184 KB
#include<bits/stdc++.h>
using namespace std;

const int N=3e5+50;
vector<int>Kra[N];
int Odw[N];
vector<int>Sciezka;

bool Por(int a, int b){
	if(a>b) return 1;
	return 0;
}

void WczytajDane(int &n, int &a, int &b){
	cin>>n>>a>>b; int d, c;
	for(int i=1; i<n; i++){
		cin>>d>>c;
		Kra[d].push_back(c);
		Kra[c].push_back(d);
	}
}

inline int LiczCzas(int v, int zak){
	Odw[v]=1;
	vector<int>Aktu;
	for(int i=0; i<(int)Kra[v].size(); i++){
		if( Odw[ Kra[v][i] ]==1 || Kra[v][i]==zak ) continue;
		Aktu.push_back( LiczCzas(Kra[v][i], zak) );	
	}
	sort( Aktu.begin(), Aktu.end(), Por );
	int wynik=0;
	for(int i=0; i<(int)Aktu.size(); i++) wynik=max( wynik, Aktu[i]+(i+1) );
	return wynik;
}

inline int ZnajdzSciezka(int v, int szukana){
	Odw[v]=1;
	Sciezka.push_back(v);
	if(v==szukana) return 1;
	
	int a;
	for(int i=0; i<(int)Kra[v].size(); i++){
		if( Odw[ Kra[v][i] ]==1 ) continue;
		a=ZnajdzSciezka(Kra[v][i], szukana);
		if(a==1) return 1;
	}
	Sciezka.pop_back();
	return 0;
}

int BS(int n, int a, int b){
	int p, k, s, s1, s2;
	p=0;
	k=(int)Sciezka.size()-2;
	while(p+1<k){
		s=(p+k)/2;
		s1=LiczCzas(a, Sciezka[s+1]);
		s2=LiczCzas(b, Sciezka[s]);
		for(int i=1; i<=n; i++) Odw[i]=0;
		if( s1<s2 ) k=s;
		else		  p=s;
	}
	if( (int)Sciezka.size()==2 ) return max( LiczCzas(a, Sciezka[1]), LiczCzas(b, Sciezka[0]) );
	
	s1=max( LiczCzas(a, Sciezka[p+1]), LiczCzas(b, Sciezka[p]) ); 
	for(int i=1; i<=n; i++) Odw[i]=0;
	s2=max( LiczCzas(a, Sciezka[p+2]), LiczCzas(b, Sciezka[p+1]) ); 
	return min(s1, s2);
}

int main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n, a, b;
	WczytajDane(n, a, b);
	ZnajdzSciezka(a, b);
	for(int i=1; i<=n; i++) Odw[i]=0;
	cout<<BS(n, a, b)<<"\n";
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 757 ms 24184 KB Output isn't correct
2 Halted 0 ms 0 KB -