Submission #474548

#	Time	Username	Problem	Language	Result	Execution time	Memory
474548		jungsnow	Torrent (COI16_torrent)	C++14	100 / 100	508 ms	25252 KiB

torrent

#include<bits/stdc++.h>
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

const int maxn = 300100, INF = 1e9;

int N, x, y, dp[maxn], par[maxn];
int banx, bany, ans = INF;
vector<int> G[maxn], a;

void prep(int u, int p = 0) {
  par[u] = p;
  for (int v : G[u]) if (v != p)
    prep(v, u);
}

void dfs(int u, int p = 0) {
  vector<int> ch;
  bool ok = (u == banx || u == bany);
  for (int v : G[u]) if (v != p) {
    if (ok && (v == banx || v == bany)) continue;
    dfs(v, u);
    ch.push_back(dp[v]);
  }
  dp[u] = 0;
  sort(ch.rbegin(), ch.rend());
  int cn = 0;
  for (int v : ch) {
    ++cn;
    dp[u] = max(dp[u], v + cn);
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("torrent.inp", "r", stdin);
//  freopen("torrent.out", "w", stdout);
  cin >> N >> x >> y;
  for (int u, v, i = 1; i < N; ++i) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  prep(x);
  int z = y;
  while (z != x) {
    a.push_back(z);
    z = par[z];
  }
  a.push_back(z);
//  for (int x : a) bug(x);
  int lo = 1, hi = a.size() - 1;
  while (lo <= hi) {
    int mi = (lo + hi) >> 1;
    banx = a[mi - 1];
    bany = a[mi];
    dfs(x);
    dfs(y);
    ans = min(ans, max(dp[x], dp[y]));
    if (dp[x] > dp[y])
      lo = mi + 1;
    else
      hi = mi - 1;
  }
  cout << ans << '\n';
}

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