/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 1.312 MiB
#2 Accepted 63ms 7.496 MiB
#3 Accepted 63ms 7.547 MiB
#4 Accepted 61ms 7.484 MiB
#5 Accepted 62ms 7.516 MiB
#6 Accepted 60ms 7.406 MiB
#7 Accepted 61ms 7.34 MiB
#8 Accepted 61ms 7.348 MiB
#9 Accepted 62ms 7.316 MiB
#10 Accepted 66ms 7.547 MiB
#11 Accepted 60ms 7.406 MiB
#12 Accepted 63ms 7.492 MiB
#13 Accepted 62ms 7.309 MiB
#14 Accepted 60ms 7.312 MiB
#15 Accepted 56ms 7.352 MiB
#16 Accepted 57ms 7.539 MiB
#17 Accepted 58ms 7.41 MiB
#18 Accepted 58ms 7.535 MiB
#19 Accepted 58ms 7.496 MiB
#20 Accepted 57ms 7.543 MiB
#21 Accepted 5ms 1.27 MiB
#22 Accepted 5ms 1.27 MiB
#23 Accepted 43ms 13.551 MiB
#24 Accepted 43ms 13.305 MiB
#25 Accepted 5ms 1.336 MiB
#26 Accepted 16ms 2.812 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-11-11 03:04:29
Judged By
Score
100
Total Time
66ms
Peak Memory
13.551 MiB