oj.uz

Submission #26254

# Submission time Handle Problem Language Result Execution time Memory
26254 2017-06-28T15:18:07 Z WhipppedCream Torrent (COI16_torrent) C++14
100 / 100
 673 ms 24684 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
vi adj[300005];
vi path;
int n, a, b;
int banfrom, banto;
int dp[300005];
void dfs(int u, int p)
{
	for(auto v: adj[u])
	{
		if(v == p) continue;
		dfs(v, u);
	}
}
bool findPath(int u, int p)
{
	if(u == b)
	{
		path.pb(u);
		return 1;
	}
	for(auto v : adj[u])
	{
		if(v == p) continue;
		if(findPath(v, u))
		{
			path.pb(u);
			return 1;
		}
	}
	return 0;
}
int solve(int u, int p)
{
	if(dp[u] != -1) return dp[u];
	vi cand;
	for(auto v : adj[u])
	{
		if(v == p) continue;
		if((u == banfrom && v == banto) || (u == banto && v == banfrom)) continue;
		cand.pb(solve(v, u));
	}
	sort(cand.begin(), cand.end());
	reverse(cand.begin(), cand.end());
	int res = 0;
	for(int i = 0; i< (int) cand.size(); i++)
	{
		res = max(res, i+1+cand[i]);
	}
	return dp[u] = res;
}
int main()
{
	scanf("%d %d %d", &n, &a, &b);
	for(int i = 0; i< n-1; i++)
	{
		int u, v; scanf("%d %d", &u, &v);
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1, 0);
	findPath(a, 0);
	reverse(path.begin(), path.end());
	int L = 0, R = ((int) path.size())-2;
	//for(auto x : path) printf("%d ", x);
	//printf("\n");
	int res = 1e9;
	while(L<= R)
	{
		memset(dp, -1, sizeof dp);
		int M = (L+R)/2;
		banfrom = path[M];
		banto = path[M+1];
		int x = solve(a, 0);
		int y = solve(b, 0);
		res = min(max(x, y), res);
		if(L == R) break;
		if(x> y) R = M-1;
		if(x< y) L = M+1;
		if(x == y) break;
	}
	printf("%d\n", res);
	return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:62:31: 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:65:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
                                   ^

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10228 KB Output is correct
2 Correct 0 ms 10228 KB Output is correct
3 Correct 6 ms 10228 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 21824 KB Output is correct
2 Correct 496 ms 22984 KB Output is correct
3 Correct 643 ms 24184 KB Output is correct
4 Correct 673 ms 23900 KB Output is correct
5 Correct 636 ms 21356 KB Output is correct
6 Correct 649 ms 22152 KB Output is correct
7 Correct 399 ms 24684 KB Output is correct