Submission #76406

#	Time	Username	Problem	Language	Result	Execution time	Memory
76406		mfbalin	Torrent (COI16_torrent)	C++17	100 / 100	976 ms	22684 KiB

torrent

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, a, b;
vector<vector<int>> g;
bool dfs(int s, vector<int> &v, int p = -1) {
	if(s == ::b)
		return true;
	v.push_back(s);
	bool b = false;
	for(auto i: g[s])
		if(i != p) {
			b = dfs(i, v, s);
			if(b)
				break;
		}
	if(!b)
		v.pop_back();
	return b;
}
int solve(int s, int p = -1) {
	vector<int> t(1, 0);
	for(auto i: g[s])
		if(i != p)
			t.push_back(solve(i, s));
	sort(t.begin(), t.end());
	int ans = t.back();
	int can = 0;
	for(int i = t.size() - 2; i >= 0; i--) {
		can += t[i + 1] - t[i] - 1;
		if(can < 0) {
			ans++;
			can = 0;
		}
	}
	return ans + 1;
}
int main(int argc, char *argv[]) {
	ios::sync_with_stdio(false);
	cin >> N >> a >> b;
	a--; b--;
	g.resize(N);
	for(int i = 1; i < N; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	vector<int> v;
	dfs(a, v);
	int l = 0, r = v.size() - 1;
	v.push_back(b);
	int ans = 1000000;
	while(l <= r) {
		int m = (l + r) / 2;
		g[v[m]].erase(find(g[v[m]].begin(), g[v[m]].end(), v[m + 1]));
		g[v[m + 1]].erase(find(g[v[m + 1]].begin(), g[v[m + 1]].end(), v[m]));
		int ta = solve(a) - 1;
		int tb = solve(b) - 1;
		ans = min(ans, max(ta, tb));
		//cerr << v[m] + 1 << ' ' << ta << ' ' << tb << endl;
		g[v[m]].push_back(v[m + 1]);
		g[v[m + 1]].push_back(v[m]);
		if(ta <= tb)
			l = m + 1;
		else
			r = m - 1;
	}
	cout << ans << '\n';
	return 0;
}

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