Submission #731089

#	Time	Username	Problem	Language	Result	Execution time	Memory
731089		Ivo_12	Torrent (COI16_torrent)	C++17	0 / 100	294 ms	38336 KiB

torrent

#include <bits/stdc++.h>

using namespace std;

int n, a, b, x, y;
vector < int > connections[300010];
vector < int > trail;

bool find_trail( int prev, int cur ) {
	if(cur == b) {
		trail.push_back(cur);
		return 1;
	}
	for(int i = 0; i < connections[cur].size(); i++) {
		if(connections[cur][i] != prev) {
			if(find_trail(cur, connections[cur][i])) {
				trail.push_back(cur);
				return 1;
			}
		}
	}
	return 0;
}

int efficient( int last, int cur, int cut ) {
	vector < int > tempmem;
	if(last == connections[cur][0] && connections[cur].size() == 1) return 0;
	if(cut == connections[cur][0] && connections[cur].size() == 1) return 0;
	for(int i = 0; i < connections[cur].size(); i++) {
		if(connections[cur][i] != last && connections[cur][i] != cut) tempmem.push_back(efficient(cur, connections[cur][i], cut));
	}
	sort(tempmem.begin(), tempmem.end());
//	cout << cur << "      ";
	for(int i = 0; i < (tempmem.size()); i++) {
		tempmem[i] += (tempmem.size())-i;
//		cout << tempmem[i] << " ";
	}
//	cout << "\n";
	return *max_element(tempmem.begin(), tempmem.end());
}

int binary_search( void ) {
	int l = 0;
	int r = trail.size() - 2;
	int mid;
	while(r > l) {
		mid = l + (r - l) / 2;
		if(efficient(-1, a, trail[mid]) >= efficient(-1, b, trail[mid+1])) r = mid;
		else l = mid + 1;
	}
	return max(efficient(-1, a, trail[l]), efficient(-1, b, trail[l+1]));
}

int main( void ) {
	
	cin >> n >> a >> b;
	for(int i = 0; i < n-1; i++) {
		cin >> x >> y;
		connections[x].push_back(y);
		connections[y].push_back(x);
	}
	find_trail(-1, a);
//	for(int i = 0; i < trail.size(); i++) {
//		cout << trail[i] << " ";
//	}
	cout << binary_search();
	
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'bool find_trail(int, int)':
torrent.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < connections[cur].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int efficient(int, int, int)':
torrent.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < connections[cur].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i = 0; i < (tempmem.size()); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~

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