oj.uz

Submission #1096722

# Submission time Handle Problem Language Result Execution time Memory
1096722 2024-10-05T04:10:24 Z ngmtuan Torrent (COI16_torrent) C++14
100 / 100
 272 ms 33204 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e5 + 5;
struct edge {
  int from, to;
};
vector<int> g[N];
vector<edge> edges;
void add_edge(int u, int v) {
  int id = (int)edges.size();
  g[u].push_back(id);
  g[v].push_back(id);
  edges.push_back({u, v});
}
int n, a, b;
int tr[N];
void dfs(int u) {
  for (int id : g[u]) {
    auto &e = edges[id];
    int v = e.from ^ e.to ^ u;
    if (tr[v] == -1) {
      tr[v] = id;
      dfs(v);
    }
  }
}

const int inf = 1e9;
int ans = inf;
int fa[N], fb[N];
int ban;

void dfs(int u, int pe, int *f) {
  vector<int> child;
  for (int id : g[u]) {
    if (id == pe || id == ban) {
      continue;
    }
    auto &e = edges[id];
    int v = e.from ^ e.to ^ u;
    child.push_back(v);
    dfs(v, id, f);
  }
  sort(child.begin(), child.end(), [&](const int &x, const int &y) {
    return f[x] > f[y];
  });
  f[u] = 0;
  for (int i = 0; i < (int)child.size(); i++) {
    f[u] = max(f[u], f[child[i]] + i + 1);
  }
}

bool check(int id) {
  ban = id;
  dfs(a, -1, fa);
  dfs(b, -1, fb);
  // cout << id << ' ' << edges[id].from << ' ' << edges[id].to << endl;
  // cout << fb[b] << ' ' << fa[a] << endl;
  ans = min(ans, max(fb[b], fa[a]));
  return fb[b] >= fa[a];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  memset(tr, -1, sizeof(tr));
  cin >> n >> a >> b;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    add_edge(u, v);
  }
  tr[a] = -2;
  dfs(a);
  vector<int> path;
  int v = b;
  while (v != a) {
    // cout << v << endl;
    path.push_back(tr[v]);
    auto &e = edges[tr[v]];
    v = e.from ^ e.to ^ v;
  }
  // cout << endl;
  int lo = 0, hi = (int)path.size() - 1, mid;
  while (lo <= hi) {
    mid = (lo + hi) >> 1;
    // cout << lo << ' ' << hi << endl;
    if (check(path[mid])) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 29244 KB Output is correct
2 Correct 272 ms 31156 KB Output is correct
3 Correct 246 ms 32956 KB Output is correct
4 Correct 250 ms 31928 KB Output is correct
5 Correct 258 ms 28600 KB Output is correct
6 Correct 242 ms 29112 KB Output is correct
7 Correct 260 ms 33204 KB Output is correct