Submission #571946

#	Time	Username	Problem	Language	Result	Execution time	Memory
571946		Shin	Torrent (COI16_torrent)	C++14	31 / 100	110 ms	40056 KiB

torrent

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 2e5 + 7;
int n, a, b;
int dp[N];
int par[N];
int flag[N];

vector<int> adj[N];

void dfs1(int u, int p) {
  par[u] = p;
  for (int v: adj[u]) if (v != p) {
    dfs1(v, u);
  }
}

void dfs2(int u, int p, int r) {
  dp[u] = 0;
  vector<int> f;
  for (int v: adj[u]) {
    if (v == p || flag[v] == r) {
      continue;
    }
    dfs2(v, u, r);
    f.push_back(dp[v]);
  }
  sort(all(f));
  reverse(all(f));
  for (int i = 0; i < (int) f.size(); i ++) {
    maximize(dp[u], f[i] + i + 1);
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> a >> b;
  for (int i = 1; i < n; i ++) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  } 

  dfs1(a, 0);
  vector<int> v;
  for (int u = b; u; u = par[u]) {
    v.push_back(u);
  }
  reverse(all(v));
  int res = n;
  auto compute = [&](int mid) {
    if (mid >= (int) v.size()) {
      return;
    }
    for (int i = 0; i <= mid; i ++) {
      flag[v[i]] = 1;
    }
    for (int i = mid + 1; i < (int) v.size(); i ++) {
      flag[v[i]] = 2;
    }
    dfs2(a, a, 2);
    dfs2(b, b, 1);
    minimize(res, max(dp[a], dp[b]));
  };
  int lo = 0, hi = (int) v.size() - 1;
  while (lo < hi) {
    int mid = (lo + hi + 1) >> 1;
    compute(mid);
    if (dp[a] <= dp[b]) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }
  compute(hi);
  compute(hi + 1);
  cout << res;
  return 0;
}

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