oj.uz

Submission #571948

# Submission time Handle Problem Language Result Execution time Memory
571948 2022-06-03T08:02:26 Z Shin Torrent (COI16_torrent) C++14
100 / 100
 495 ms 30016 KB 
#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 = 3e5 + 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.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 22084 KB Output is correct
2 Correct 495 ms 27692 KB Output is correct
3 Correct 415 ms 29588 KB Output is correct
4 Correct 452 ms 28820 KB Output is correct
5 Correct 426 ms 25860 KB Output is correct
6 Correct 407 ms 26484 KB Output is correct
7 Correct 409 ms 30016 KB Output is correct