oj.uz

Submission #101072

# Submission time Handle Problem Language Result Execution time Memory
101072 2019-03-16T11:02:26 Z JedrzejOlkowski Torrent (COI16_torrent) C++14
100 / 100
 743 ms 26020 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]);
		
	//	cout << "S " << s << ": " << Sciezka[s] << " " << Sciezka[s+1] << endl;
	//	cout << s1 << "-" << s2 << endl;
		
		for(int i=1; i<=n; i++) Odw[i]=0;
		if( s1<s2 ) p=s;
		else		  k=s;
	}
	
//	for(int i=0; i<(int)Sciezka.size(); i++) cout << Sciezka[i] << " ";
//	cout << endl;
	
	if( (int)Sciezka.size()==2 ) return max( LiczCzas(a, Sciezka[1]), LiczCzas(b, Sciezka[0]) );
	
//	cout << Sciezka[p] << " " << Sciezka[p+1] << " " << Sciezka[p+2] << endl;
	
	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;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 12 ms 7424 KB Output is correct
3 Correct 11 ms 7424 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 20016 KB Output is correct
2 Correct 743 ms 24676 KB Output is correct
3 Correct 702 ms 25784 KB Output is correct
4 Correct 655 ms 25336 KB Output is correct
5 Correct 627 ms 23544 KB Output is correct
6 Correct 612 ms 24116 KB Output is correct
7 Correct 543 ms 26020 KB Output is correct