제출 #731098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731098		Ivo_12	Torrent (COI16_torrent)	C++98	0 / 100	451 ms	19132 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;
	if(connections[cur].size()==2) {
		if(cut == connections[cur][0] && last == connections[cur][1]) return 0;
		if(last == connections[cur][0] && cut == connections[cur][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]));
	
	// greska, run time error i trebas isprobati za l-1 s obzirom da vracas prvi veci a mozda ce i prvi manji biti dobar
}

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;
}

컴파일 시 표준 에러 (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:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < connections[cur].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:38:19: 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 < (tempmem.size()); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~

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