Submission #211606

#	Time	Username	Problem	Language	Result	Execution time	Memory
211606		Fischer	Torrent (COI16_torrent)	C++14	31 / 100	516 ms	27084 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
vector<int> p, g[maxn];
int n, a, b;
bool vis[maxn];
int dp[maxn];

bool get_path(int x, int y, int p, vector<int>& P) {
	if (x == y) return 1;
	for (int& v : g[x]) {
		if (v == p) continue;
		P.emplace_back(v);
		if (get_path(v, y, x, P)) return 1;
		P.pop_back();
	}
	return 0;
}

int dfs(int x, int p=0) {
	vector<int> t;
	for (int v : g[x]) {
		if (v == p) continue;
		t.push_back(dfs(v, x));
	}
	sort(t.rbegin(), t.rend());
	dp[x] = 0;
	for (int i = 0; i < t.size(); ++i) {
		dp[x] = max(dp[x], t[i] + i + 1);
	}
	return dp[x];
}

void remov(int x, int v) {
	for (int& u : g[x]) {
		if (u == v) {
			swap(g[x].back(), u);
			break;
		}
	}
	g[x].pop_back();
}	

int x, y;
int f(int t) {
	remov(p[t], p[t+1]);
	remov(p[t+1], p[t]);
	x = dfs(a);
	y = dfs(b);
	int ans = x < y;
	g[p[t]].emplace_back(p[t+1]);
	g[p[t+1]].emplace_back(p[t]);
	return ans;
}

int main() {
	scanf("%d%d%d", &n, &a, &b);
	for (int i = 0; i < n-1; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		g[x].emplace_back(y);
		g[y].emplace_back(x);
	}	
	p = {a};
	get_path(a, b, 0, p);
	int lo = 0, hi = p.size() - 2;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (f(mid)) lo = mid+1;
		else hi = mid;
	}	
	int ans = INT_MAX;
	f(lo);
	ans = max(x, y);
	if (lo + 3 < p.size()) {
		f(lo+1);
		ans = min(ans, max(x, y));
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int dfs(int, int)':
torrent.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < t.size(); ++i) {
                  ~~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:75:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (lo + 3 < p.size()) {
      ~~~~~~~^~~~~~~~~~
torrent.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

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