oj.uz

Submission #531594

# Submission time Handle Problem Language Result Execution time Memory
531594 2022-03-01T05:55:31 Z colazcy Torrent (COI16_torrent) C++17
100 / 100
 666 ms 27752 KB 
#include <iostream>
#include <cassert>
#include <vector>
#include <functional>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 3e5 + 10;

std::vector<int> G[maxn],seq;
void addedge(const int u,const int v){G[u].push_back(v);}
int n,s,t;
bool dfs(const int u,const int faz = -1){
	seq.push_back(u);
	if(u == t)return true;
	for(let v : G[u]){
		if(v == faz)continue;
		if(dfs(v,u))return true;
	}
	seq.pop_back();
	return false;
}


std::pair<int,int> solve(const int lim){
	// assert(seq.size() >= 2);
	// assert(lim >= 0);
	
	let du = seq[lim],dv = seq[lim + 1];
	std::function<int(const int,const int)> dp = [du,dv,&dp](const int u,const int faz){
		std::vector<int> vec;
		vec.reserve(G[u].size());
		for(let v : G[u]){
			if(u == du && v == dv)continue;
			if(u == dv && v == du)continue;
			if(v == faz)continue;
			vec.push_back(dp(v,u));
		}
		int res = 0,tot = 0;
		std::sort(vec.begin(),vec.end(),std::greater<int>());
		for(let x : vec)
			res = std::max(res,x + (++tot));
		// debug("res = %d\n",res);
		return res;
	};
	return std::make_pair(dp(s,-1),dp(t,-1));	
}
int main(){
	// std::freopen("torrent.in","r",stdin);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n >> s >> t;
	repn(n - 1){
		int u,v; std::cin >> u >> v;
		addedge(u,v);
		addedge(v,u);
	}
	dfs(s);	
	int l = 0,r = seq.size() - 2,ans = -1;
	while(l <= r){
		let mid = (l + r) >> 1;
		let [f,g] = solve(mid);
		if(f <= g)ans = mid,l = mid + 1;
		else r = mid - 1;
	}
	int out = 0x7fffffff;
	if(ans != -1)out = std::min(out,solve(ans).second);
	if(ans + 1 != (int)seq.size() - 1)out = std::min(out,solve(ans + 1).first);
	std::cout << out  << "\n";
	return 0;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 22448 KB Output is correct
2 Correct 666 ms 25680 KB Output is correct
3 Correct 592 ms 27480 KB Output is correct
4 Correct 519 ms 26596 KB Output is correct
5 Correct 498 ms 23196 KB Output is correct
6 Correct 466 ms 23708 KB Output is correct
7 Correct 440 ms 27752 KB Output is correct