Submission #169508

#	Time	Username	Problem	Language	Result	Execution time	Memory
169508		algorithm16	Torrent (COI16_torrent)	C++14	0 / 100	1111 ms	23112 KiB

torrent

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
vector <int> v[300005];
vector <int> v1;
int cnt[2][300005],bio[300005];
bool sort_function1(int a,int b) {
	return cnt[0][a]>cnt[0][b];
}
bool sort_function2(int a,int b) {
	return cnt[1][a]>cnt[1][b];
}
int dfs(int x,int par,int c) {
	//if(par==133119) cout << par << " " << x << "\n";
	//if(x==133120) cout << x << "\n";
	//if(x==133120) cout << x << " " << bio[x] << "\n";
	bio[x]=1;
	if(x==c) return 1;
	int ret=0;
	for(int i=0;i<v[x].size();i++) {
		//if(x==133119) cout << "a\n";
		if(v[x][i]==par or bio[v[x][i]]) continue;
		//if(x==133119) cout << v[x][i] << "\n";
		if(dfs(v[x][i],x,c)) {
			ret+=1;
			v1.push_back(v[x][i]);
		}
	}
	return ret;
}
int f(int x,int par,int ind) {
	//cout << x << " " << ind << "\n";
	int ret=1;
	for(int i=0;i<v[x].size();i++) {
		if(v[x][i]==par) continue;
		ret+=f(v[x][i],x,ind);
	}
	cnt[ind][x]=ret;
	return ret;
}
int eval(int x,int par,int ind) {
	//cout << x << "\n";
	int ret=0,y=0;
	if(ind) sort(v[x].begin(),v[x].end(),sort_function2);
	else sort(v[x].begin(),v[x].end(),sort_function1);
	for(int i=0;i<v[x].size();i++) {
		if(v[x][i]==par) continue;
		//cout << v[x][i] << " " << cnt[ind][v[x][i]] << "\n";
		ret=max(ret,eval(v[x][i],x,ind)+1+y);
		y+=1;
	}
	//cout << x << " " << ret << "\n";
	//cout << "\n\n";
	return ret;
}
int main()
{
	int n,a,b,sol=0;
	cin >> n >> a >> b;
	a-=1;
	b-=1;
	for(int i=0;i<n-1;i++) {
		int x,y;
		cin >> x >> y;
		v[x-1].push_back(y-1);
		v[y-1].push_back(x-1);
	}
	//cout << "1\n";
	dfs(a,-1,b);
	//cout << "2\n";
	v1.push_back(a);
	reverse(v1.begin(),v1.end());
	int lo=1,hi=v1.size()-1;
	//cout << "a\n";
	/*cout << "\n";
	for(int i=0;i<n;i++) {
		cout << i+1 << " " << cnt[1][i] << "\n";
	}
	cout << "\n";*/
	if(lo>=hi) {
		v[a].erase(find(v[a].begin(),v[a].end(),b));
		v[b].erase(find(v[b].begin(),v[b].end(),a));
		f(a,-1,0);
		f(b,-1,1);
		cout << max(eval(a,-1,0),eval(b,-1,1));
		//cout << eval(a,-1,0) << " " << eval(b,-1,1) << "\n";
		return 0;
	}
	//cout << "b\n";
	while(lo<hi) {
		int mid=(lo+hi)/2;
		if(hi-lo==1) mid=hi;
		if(mid>0 && mid<v1.size()) {
			v[v1[mid-1]].erase(find(v[v1[mid-1]].begin(),v[v1[mid-1]].end(),v1[mid]));
			v[v1[mid]].erase(find(v[v1[mid]].begin(),v[v1[mid]].end(),v1[mid-1]));
		}
		memset(cnt,0,sizeof(cnt));
		f(a,-1,0);
		f(b,-1,1);
		//cout << mid << " " << eval(a,-1,0) << " " << eval(b,-1,1) << "\n";
		if(eval(a,-1,0)>=eval(b,-1,1)) {
			lo=mid;
			sol=eval(a,-1,0);
		}
		else {
			hi=mid-1;
			sol=eval(b,-1,1);
		}
	}
	cout << sol;
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int dfs(int, int, int)':
torrent.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int f(int, int, int)':
torrent.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int eval(int, int, int)':
torrent.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(mid>0 && mid<v1.size()) {
               ~~~^~~~~~~~~~

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