Submission #531593

#	Time	Username	Problem	Language	Result	Execution time	Memory
531593		colazcy	Torrent (COI16_torrent)	C++17	31 / 100	37 ms	12912 KiB

torrent

#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 = 1e5 + 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 / 31
• Subtask 2: 0 / 69