oj.uz

Submission #211607

# Submission time Handle Problem Language Result Execution time Memory
211607 2020-03-20T19:29:42 Z Fischer Torrent (COI16_torrent) C++14
100 / 100
 539 ms 23404 KB 
#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 - 1 >= 0) {
		f(lo-1);
		ans = min(ans, max(x, y));
	}
	cout << ans << endl;
	return 0;
}

Compilation message

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: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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 20660 KB Output is correct
2 Correct 539 ms 22028 KB Output is correct
3 Correct 509 ms 23260 KB Output is correct
4 Correct 537 ms 22624 KB Output is correct
5 Correct 513 ms 20164 KB Output is correct
6 Correct 472 ms 20904 KB Output is correct
7 Correct 476 ms 23404 KB Output is correct