oj.uz

Submission #474548

# Submission time Handle Problem Language Result Execution time Memory
474548 2021-09-19T02:39:34 Z jungsnow Torrent (COI16_torrent) C++14
100 / 100
 508 ms 25252 KB 
#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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7348 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 21724 KB Output is correct
2 Correct 508 ms 23212 KB Output is correct
3 Correct 465 ms 24888 KB Output is correct
4 Correct 491 ms 24588 KB Output is correct
5 Correct 430 ms 21208 KB Output is correct
6 Correct 415 ms 21824 KB Output is correct
7 Correct 440 ms 25252 KB Output is correct