Submission #76400

# Submission time Handle Problem Language Result Execution time Memory
76400 2018-09-13T12:41:51 Z mfbalin Torrent (COI16_torrent) C++17
0 / 100
1049 ms 19588 KB
#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();
	for(int i = t.size() - 2; i >= 0; i--)
		if(t[i] == t[i + 1])
			ans++;
	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(l == r)
			break;
		if(ta < tb)
			l = m + 1;
		else
			r = m;
	}
	cout << ans << '\n';
	return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1049 ms 19588 KB Output isn't correct
2 Halted 0 ms 0 KB -