oj.uz

Submission #111157

# Submission time Handle Problem Language Result Execution time Memory
111157 2019-05-14T00:33:48 Z luciocf Torrent (COI16_torrent) C++14
100 / 100
 708 ms 26040 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5+10;

int n;
int A, B;

vector<int> grafo[maxn];
vector<int> path;

bool comp(int a, int b) {return a>b;}

bool dfs(int u, int p)
{
	if (u == B)
	{
		path.push_back(B);
		return 1;
	}

	for (auto v: grafo[u])
	{
		if (v == p) continue;
		if (!dfs(v, u)) continue;

		path.push_back(u);
		return 1;
	}

	return 0;
}

int solve(int u, int p, int block)
{
	vector<int> child;

	int tt = 0;

	for (auto v: grafo[u])
		if (v != p && v != block)
			child.push_back(solve(v, u, block));

	sort(child.begin(), child.end(), comp);

	for (int i = 0; i < child.size(); i++)
		tt = max(tt, child[i]+i+1);

	return tt;
}

int busca(void)
{
	int ini = 1, fim = path.size()-1, ans = -1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		int ans1 = solve(A, 0, path[mid]);
		int ans2 = solve(B, 0, path[mid-1]);

		if (ans2 >= ans1) ans = mid-1, ini = mid+1;
		else fim = mid-1;
	}

	return ans;
}

int main(void)
{
	scanf("%d %d %d", &n, &A, &B);

	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	dfs(A, 0);
	reverse(path.begin(), path.end());

	int opt = busca();

	int ans;

	if (opt == -1)
		ans = solve(A, 0, path[1]);
	else
	{
		ans = solve(B, 0, path[opt]);
		if (opt < path.size()-2)
			ans = min(ans, solve(A, 0, path[opt+2]));
	}

	printf("%d\n", ans);
}

Compilation message

torrent.cpp: In function 'int solve(int, int, int)':
torrent.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < child.size(); i++)
                  ~~^~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:96:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (opt < path.size()-2)
       ~~~~^~~~~~~~~~~~~~~
torrent.cpp:73: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:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 18908 KB Output is correct
2 Correct 618 ms 20184 KB Output is correct
3 Correct 616 ms 21444 KB Output is correct
4 Correct 683 ms 25148 KB Output is correct
5 Correct 694 ms 22648 KB Output is correct
6 Correct 708 ms 23292 KB Output is correct
7 Correct 566 ms 26040 KB Output is correct