/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 320.0 KiB
#2 Wrong Answer 46ms 7.109 MiB
#3 Wrong Answer 47ms 7.156 MiB
#4 Wrong Answer 48ms 7.137 MiB
#5 Accepted 51ms 7.062 MiB
#6 Wrong Answer 47ms 7.113 MiB
#7 Wrong Answer 48ms 7.176 MiB
#8 Wrong Answer 48ms 7.121 MiB
#9 Wrong Answer 48ms 7.184 MiB
#10 Wrong Answer 47ms 7.008 MiB
#11 Wrong Answer 47ms 7.051 MiB
#12 Wrong Answer 48ms 7.164 MiB
#13 Accepted 46ms 7.055 MiB
#14 Wrong Answer 47ms 7.082 MiB
#15 Accepted 47ms 7.047 MiB
#16 Wrong Answer 47ms 7.199 MiB
#17 Wrong Answer 48ms 7.078 MiB
#18 Wrong Answer 49ms 7.059 MiB
#19 Wrong Answer 50ms 7.059 MiB
#20 Wrong Answer 48ms 7.066 MiB
#21 Accepted 1ms 320.0 KiB
#22 Wrong Answer 1ms 320.0 KiB
#23 Wrong Answer 31ms 6.914 MiB
#24 Wrong Answer 33ms 7.027 MiB
#25 Wrong Answer 2ms 364.0 KiB
#26 Wrong Answer 12ms 1.938 MiB

Code

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

void solve(int cs) {
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  auto bfs = [&](int start) -> pair<int, vector<int>> {
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    int farthest_node = start;
    int farthest = 0;

    while (!q.empty()) {
      int node = q.front();
      q.pop();

      for (int it : g[node]) {
        if (dist[it] == -1) {
          q.push(it);
          dist[it] = dist[node] + 1;

          if (dist[it] > farthest) {
            farthest = dist[it];
            farthest_node = it;
          }
        }
      }
    }

    return {farthest_node, dist};
  };

  auto [first, distA] = bfs(0);
  auto [second, distB] = bfs(first);

  int diameter = distB[second];

  int center = second;
  for (int i = 0; i < diameter / 2; ++i) {
    center = g[center][0];
  }
  cout << (diameter + 1) / 2 << " " << center + 1 << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc = 1;
  // cin >> tc;
  for (int cs = 1; cs <= tc; cs++) {
    solve(cs);
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1069 Vaccination
Contest
Brain Booster #4
Language
C++20 (G++ 13.2.0)
Submit At
2024-07-14 17:08:12
Judged At
2024-10-03 13:36:21
Judged By
Score
21
Total Time
51ms
Peak Memory
7.199 MiB