/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 324.0 KiB
#2 Wrong Answer 50ms 7.18 MiB
#3 Accepted 49ms 7.207 MiB
#4 Accepted 48ms 7.141 MiB
#5 Accepted 50ms 7.211 MiB
#6 Accepted 48ms 7.199 MiB
#7 Wrong Answer 52ms 7.199 MiB
#8 Wrong Answer 51ms 7.164 MiB
#9 Wrong Answer 51ms 7.113 MiB
#10 Wrong Answer 51ms 7.086 MiB
#11 Accepted 49ms 7.148 MiB
#12 Accepted 50ms 7.18 MiB
#13 Accepted 52ms 7.109 MiB
#14 Wrong Answer 51ms 7.137 MiB
#15 Accepted 56ms 7.133 MiB
#16 Wrong Answer 49ms 7.137 MiB
#17 Wrong Answer 50ms 7.203 MiB
#18 Wrong Answer 50ms 7.172 MiB
#19 Wrong Answer 50ms 7.082 MiB
#20 Wrong Answer 48ms 7.102 MiB
#21 Wrong Answer 1ms 532.0 KiB
#22 Wrong Answer 1ms 348.0 KiB
#23 Wrong Answer 32ms 7.316 MiB
#24 Accepted 32ms 7.449 MiB
#25 Wrong Answer 1ms 324.0 KiB
#26 Wrong Answer 11ms 2.062 MiB

Code

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
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);
  }
  vector<int> dist(n), par(n);
  auto bfs = [&](int st) -> vector<int> {
    dist.assign(n, -1);
    queue<int> q;
    q.push(st);
    dist[st] = 0;
    vector<int> par(n, -1);
    int farthest = st;
    while (q.size()) {
      int node = q.front();
      q.pop();
      for (auto it : g[node]) {
        if (dist[it] == -1) {
          q.push(it);
          par[it] = node;
          dist[it] = dist[node] + 1;
          if (dist[it] > dist[farthest]) {
            farthest = it;
          }
        }
      }
    }
    return par;
  };
  par = bfs(1);
  int A = max_element(dist.begin(), dist.end()) - dist.begin();
  par = bfs(A);
  int B = max_element(dist.begin(), dist.end()) - dist.begin();
  vector<int> path;
  for (int v = B; v != -1; v = par[v]) {
    path.push_back(v);
  }
  int len = path.size();
  int days = (len - 1) / 2;
  int node = path[len / 2];
  if (len % 2 == 0) {
    node = max(node, path[len / 2 - 1]);
  }
  cout << days << " " << node + 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:00:58
Judged At
2024-10-03 13:36:33
Judged By
Score
46
Total Time
56ms
Peak Memory
7.449 MiB