Submission #743373

#	Time	Username	Problem	Language	Result	Execution time	Memory
743373		drkarlicio2107	Torrent (COI16_torrent)	C++14	100 / 100	631 ms	29476 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
int n, a, b;
vector < int > g [300010];
int l [300010];
int dp [300010];
vector <int> pom;
int mark_path (int x, int par){
	if (x==a) return l [x]=0;
	int ret=-1;
	for (int i=0; i<g [x].size(); i++){
		int y=g [x][i];
		if (y==par) continue;
		int val=mark_path (y, x);
		if (val!=-1) ret=val+1;
	}
	return l [x]=ret;
}
int rek (int x, int mid, int par, int od, int sus){
	vector <int> my; my.clear ();
	for (int i=0; i<g [x].size(); i++){
		int y=g [x][i];
		if (y==par) continue;
		if (sus && l [y]!=-1) continue;
		if (l [y]==mid){
			if (od && dp [y]==-1) my.push_back (rek (y, mid, x, od, 1));
			continue;
		}
		if (l [x]==mid){
			if (l [y]==mid+1 || (l [y]==mid-1 && mid-1!=-1)){
				continue;
			}
		}
		my.push_back (rek (y, mid, x, od, sus));
	}
	sort (my.begin(), my.end()); reverse (my.begin(), my.end());
	int sol=0;
	for (int i=0; i<my.size(); i++) sol=max (sol, my [i]+(i+1));
	return dp [x]=sol;
}
int main(){
	memset (l, -1, sizeof l);
	cin >> n >> a >> b;
	for (int i=0; i<n-1; i++){
		int x, y; cin >> x >> y;
		g [x].push_back (y);
		g [y].push_back (x);
	}
	mark_path (b, -1);
	/*cout << "Prosao: " << endl;
	for (int i=1; i<n+1; i++) cout << l [i] << " ";
	cout << endl;*/ 
	int lo=0; int hi=l [b];
	while (lo!=hi){
		int mid=(lo+hi)/2;
		memset (dp, -1, sizeof dp); int sol1=rek (a, mid, -1, 0, 0); 
		int sol2=rek (b, mid, -1, 1, 0); 
		if (sol1<sol2) lo=mid+1;
		else hi=mid;
		//cout << lo << " " << hi << endl;
	}
	memset (dp, -1, sizeof dp); int sol1=rek (a, lo, -1, 0, 0); 
	int sol2=rek (b, lo, -1, 1, 0);
	memset (dp, -1, sizeof dp); int sol4=rek (a, lo-1, -1, 0, 0); 
	int sol5=rek (b, lo-1, -1, 1, 0);
	//cout << lo << " " << sol1 << " " << sol2 << " " << sol3 << endl;
	cout << min (max (sol1, sol2), max (sol4, sol5)) << endl;
}

Compilation message (stderr)

torrent.cpp: In function 'int mark_path(int, int)':
torrent.cpp:11:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for (int i=0; i<g [x].size(); i++){
      |                ~^~~~~~~~~~~~~
torrent.cpp: In function 'int rek(int, int, int, int, int)':
torrent.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i=0; i<g [x].size(); i++){
      |                ~^~~~~~~~~~~~~
torrent.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i=0; i<my.size(); i++) sol=max (sol, my [i]+(i+1));
      |                ~^~~~~~~~~~

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