oj.uz

Submission #764148

# Submission time Handle Problem Language Result Execution time Memory
764148 2023-06-23T07:48:43 Z myrcella Torrent (COI16_torrent) C++17
100 / 100
 350 ms 23436 KB 
// by szh
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}

const int maxn = 3e5+10;

int n;
vector <int> edge[maxn];
int cnt = 0;
int x, y;
int dp[maxn];
int ans = 0;
int uu, vv;

int solve(int u, int fa) {
  vector <int> val;
  for (auto v : edge[u]) {
	if (v == fa) continue;
	if (uu == u and vv == v) continue;
	if (uu == v and vv == u) continue;
	solve(v, u);
	val.pb(dp[v]);
  }
  //debug(u), debug(SZ(val));
  sort(ALL(val));
  reverse(ALL(val));
  dp[u] = 0;
  rep(i, 0, SZ(val)) dp[u] = max(dp[u], val[i] + i + 1);
  //debug(dp[u]);
  return dp[u];
}

vector <int> node;

bool dfs(int u, int fa) {
  if (u == y) node.pb(u);
  if (u == y) return true;
  for (int v : edge[u]) {
	if (v == fa) continue;
	if (dfs(v, u)) {
	  node.pb(u);
	  return true;
    }
  }
  return false;
}

int main() {
  // freopen("input.txt","r",stdin);
  std::ios::sync_with_stdio(false); cin.tie(0);
  memset(dp, -1, sizeof(dp));
  cin >> n >> x >> y;
  rep(i, 1, n) {
	int u, v;
	cin >> u >> v;
	edge[u].pb(v);
	edge[v].pb(u);
  }
  dfs(x, -1);
  uu = -1, vv = -1;
  if (SZ(node) == 2) {
	ans = max(solve(x, y), solve(y, x));
	cout << ans;
	return 0;
  }
  int l = 0, r = SZ(node) - 2;
  ans = n;
  while (l < r) {
	int mid = l + r + 1 >> 1;
	uu = node[mid], vv = node[mid+1];
	int tmp1 = solve(node[0], -1), tmp2 = solve(node.back(), -1);
	//debug(uu), debug(vv);
	//debug(dp[3]), debug(dp[4]), debug(dp[13]);
	//debug(mid), debug(tmp1), debug(tmp2);
	ans = min(ans, max(tmp1, tmp2));
	if (tmp1 < tmp2) l = mid;
	else r = mid-1;
  }
  l++;
  if (l < SZ(node) - 1) {
	uu = node[l], vv = node[l+1];
	int tmp1 = solve(node[0], -1), tmp2 = solve(node.back(), -1);
	ans = min(ans, max(tmp1, tmp2));
  }
  cout << ans << "\n";
  return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int mid = l + r + 1 >> 1;
      |            ~~~~~~^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Correct 5 ms 8532 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 20344 KB Output is correct
2 Correct 304 ms 21704 KB Output is correct
3 Correct 304 ms 23144 KB Output is correct
4 Correct 286 ms 22536 KB Output is correct
5 Correct 317 ms 19748 KB Output is correct
6 Correct 261 ms 20388 KB Output is correct
7 Correct 257 ms 23436 KB Output is correct