oj.uz

Submission #900616

# Submission time Handle Problem Language Result Execution time Memory
900616 2024-01-08T16:22:45 Z LCJLY Torrent (COI16_torrent) C++14
100 / 100
 284 ms 29936 KB 
#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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 27056 KB Output is correct
2 Correct 284 ms 28224 KB Output is correct
3 Correct 245 ms 29388 KB Output is correct
4 Correct 251 ms 28884 KB Output is correct
5 Correct 240 ms 26380 KB Output is correct
6 Correct 247 ms 27132 KB Output is correct
7 Correct 260 ms 29936 KB Output is correct