Submission #246447

#	Time	Username	Problem	Language	Result	Execution time	Memory
246447		vanic	Torrent (COI16_torrent)	C++14	31 / 100	2082 ms	25080 KiB

torrent

#include <cstdio>
#include <math.h>
#include <algorithm>
#include <bitset>
#include <vector>
#include <assert.h>

using namespace std;

const int maxn=3e5+5;

int n, a, b;
vector < int > ms[maxn];
vector < int > put;
int val[maxn];
bitset < maxn > bio;
vector < int > svi;

bool dfs(int x, int prosl){
	put.push_back(x);
	if(x==b){
		return 1;
	}
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			if(dfs(ms[x][i], x)){
				return 1;
			}
		}
	}
	put.pop_back();
	return 0;
}

int siri(int x, int prosl){
	int sz=0;
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i]!=prosl && !bio[ms[x][i]]){
			sz++;
			svi.push_back(siri(ms[x][i], x));
		}
	}
	sort(svi.end()-sz, svi.end());
	val[x]=1;
	int br=1;
	while(br<=sz){
		if(val[x]<svi.back()+br){
			val[x]=svi.back()+br;
		}
		br++;
		svi.pop_back();
	}
	return val[x];
}

int main(){
	scanf("%d%d%d", &n, &a, &b);
	a--;
	b--;
	int c, d;
	for(int i=0; i<n-1; i++){
		scanf("%d%d", &c, &d);
		c--;
		d--;
		ms[c].push_back(d);
		ms[d].push_back(c);
	}
	dfs(a, a);
	int sol=1e9;
	int br1, br2;
	for(int i=0; i<put.size()-1; i++){
		bio[put[i+1]]=1;
		br1=siri(a, a);
		br1--;
		bio[put[i+1]]=0;
		bio[put[i]]=1;
		br2=siri(b, b);
		bio[put[i]]=0;
		br2--;
		sol=min(sol, max(br1, br2));
	}
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'bool dfs(int, int)':
torrent.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
torrent.cpp: In function 'int siri(int, int)':
torrent.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<put.size()-1; i++){
               ~^~~~~~~~~~~~~
torrent.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~

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