oj.uz

Submission #1081385

# Submission time Handle Problem Language Result Execution time Memory
1081385 2024-08-30T03:18:28 Z juicy Torrent (COI16_torrent) C++17
100 / 100
 308 ms 30648 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 3e5 + 5;

int n, m, a, b;
int pr[N], lab[N], dp[N];
vector<int> g[N], cands;

void dfs(int u) {
  for (int v : g[u]) {
    if (v ^ pr[u]) {
      pr[v] = u;
      dfs(v);
    }
  }
}

vector<int> qry(int u, int v) {
  vector<int> p;
  while (u != pr[v]) {
    p.push_back(u);
    u = pr[u];
  }
  return p;
}

void dfs(int u, int t) {
  vector<int> c;
  for (int v : g[u]) {
    if (v != pr[u] && lab[v] != 1 - t) {
      pr[v] = u;
      dfs(v, t);
      c.push_back(dp[v]);
    }
  }
  sort(c.rbegin(), c.rend());
  dp[u] = 0;
  for (int i = 0; i < c.size(); ++i) {
    dp[u] = max(dp[u], c[i] + i + 1); 
  }
}

array<int, 2> calc(int k) {
  for (int i = 0; i < m; ++i) {
    lab[cands[i]] = i > k;
  }
  pr[a] = 0; dfs(a, 0);
  pr[b] = 0; dfs(b, 1);
  return {dp[a], dp[b]};
}

int qry(int k) {
  auto [x, y] = calc(k);
  return max(x, y);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> a >> b;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(b);
  cands = qry(a, b);
  m = cands.size();
  memset(lab, -1, sizeof(lab));
  int l = 0, r = m - 2, p = 0;
  while (l <= r) {
    int md = (l + r) / 2;
    auto x = calc(md);
    if (x[0] <= x[1]) {
      p = md;
      l = md + 1;
    } else {
      r = md - 1;
    }
  }
  cout << (min(qry(p), p + 2 < m ? qry(p + 1) : n));
  return 0;
}

Compilation message

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for (int i = 0; i < c.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 26980 KB Output is correct
2 Correct 243 ms 28592 KB Output is correct
3 Correct 256 ms 30292 KB Output is correct
4 Correct 275 ms 29628 KB Output is correct
5 Correct 239 ms 26300 KB Output is correct
6 Correct 254 ms 27184 KB Output is correct
7 Correct 251 ms 30648 KB Output is correct