/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 1.27 MiB
#2 Accepted 47ms 7.52 MiB
#3 Accepted 68ms 7.539 MiB
#4 Accepted 79ms 7.43 MiB
#5 Accepted 45ms 7.402 MiB
#6 Accepted 73ms 7.332 MiB
#7 Accepted 43ms 7.477 MiB
#8 Accepted 46ms 7.52 MiB
#9 Accepted 46ms 7.77 MiB
#10 Accepted 42ms 7.387 MiB
#11 Accepted 42ms 7.52 MiB
#12 Accepted 43ms 7.312 MiB
#13 Accepted 44ms 7.387 MiB
#14 Accepted 44ms 7.398 MiB
#15 Accepted 48ms 7.379 MiB
#16 Accepted 44ms 7.348 MiB
#17 Accepted 44ms 7.398 MiB
#18 Accepted 69ms 7.539 MiB
#19 Accepted 43ms 7.551 MiB
#20 Accepted 51ms 7.473 MiB
#21 Accepted 4ms 1.27 MiB
#22 Accepted 14ms 1.332 MiB
#23 Accepted 41ms 13.457 MiB
#24 Accepted 62ms 13.426 MiB
#25 Accepted 4ms 1.27 MiB
#26 Accepted 14ms 2.77 MiB

Code

#include <bits/stdc++.h>
using namespace std;

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using ll = long long;

const int MX = 200005;
vector<int> g[MX];
int dis[MX];
int in[MX], out[MX], timer;

void dfs(int u, int p = -1) {
  in[u] = timer++;
  for (int v : g[u]) {
    if (v == p) continue;
    dis[v] = dis[u] + 1;
    dfs(v, u);
  }
  out[u] = timer-1;
}

int main() {
  FAST;

  int n, i, u, v, x, ans;
  cin >> n;

  for (i = 1; i < n; ++i) {
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  memset(dis, 0, sizeof(dis));
  timer = 0;
  dfs(0);
  u = 0;
  for (i = 0; i < n; ++i) {
    if (dis[i] > dis[u]) u = i;
  }

  memset(dis, 0, sizeof(dis));
  timer = 0;
  dfs(u);
  v = u;
  for (i = 0; i < n; ++i) {
    if (dis[i] > dis[v]) v = i;
  }

  ans = 0;

  x = dis[v] / 2;
  for (i = 0; i < n; ++i) {
    if ((dis[i] == x) && (in[i] <= in[v]) && (in[v] <= out[i])) {
      ans = max(ans, i);
    }
  }

  if (dis[v] & 1) {
    x = (dis[v] + 1) / 2;
    for (i = 0; i < n; ++i) {
      if ((dis[i] == x) && (in[i] <= in[v]) && (in[v] <= out[i])) {
        ans = max(ans, i);
      }
    }
  }

  cout << x << " " << ans+1 << "\n";

  return 0;
}

Information

Submit By
Type
Submission
Problem
P1069 Vaccination
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-04 11:22:41
Judged At
2024-09-04 11:22:41
Judged By
Score
100
Total Time
79ms
Peak Memory
13.457 MiB