Submission #900616

#	Time	Username	Problem	Language	Result	Execution time	Memory
900616		LCJLY	Torrent (COI16_torrent)	C++14	100 / 100	284 ms	29936 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;
typedef pair<pii,pii>pi2;

int n,a,b;
vector<int>adj[300005];
int pp[300005];

void dfs(int index, int par){
	for(auto it:adj[index]){
		if(it==par) continue;
		pp[it]=index;
		dfs(it,index);
	}
}

int best=INT_MAX;
pii edge; //ban edge

int dp(int index, int par){
	int hold=0;
	vector<int>child;
	for(auto it:adj[index]){
		if(it==par) continue;
		if(it==edge.first&&index==edge.second) continue;
		if(it==edge.second&&index==edge.first) continue;
		child.push_back(dp(it,index));
	}
	sort(child.begin(),child.end());
	reverse(child.begin(),child.end());
	for(int x=0;x<(int)child.size();x++){
		hold=max(hold,child[x]+x+1);
	}
	return hold;
}

void solve(){	
	cin >> n >> a >> b;
	
	int temp,temp2;
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2;
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
	}
	
	dfs(a,-1);
	
	int cur=b;
	vector<int>v;
	
	while(1){
		v.push_back(cur);
		if(cur==a) break;
		cur=pp[cur];
	}
	
	int l=0;
	int r=v.size()-2;
	int mid;
	
	while(l<=r){
		mid=(l+r)/2;
		edge.first=v[mid];
		edge.second=v[mid+1];
	
		int hold=dp(a,-1);
		int hold2=dp(b,-1);
		best=min(best,max(hold,hold2));
		if(hold2>hold){
			r=mid-1;
		}
		else l=mid+1;
	}
	
	cout << best;
}	

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

		

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