oj.uz

Submission #904054

# Submission time Handle Problem Language Result Execution time Memory
904054 2024-01-11T19:00:23 Z vjudge1 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 140 ms 22736 KB 
#include <bits/stdc++.h>

using namespace std;

struct UnionFind {
  int n;
  vector<int> parent;
  vector<int> S;
  UnionFind(int n) : n(n) {
    parent.resize(n);
    S.resize(n, 1);
    for (int i = 0; i < n; i++)
      parent[i] = i;
  }
  int Find(int x) {
    if (x != parent[x])
      parent[x] = Find(parent[x]);
    return parent[x];
  }
  void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a == b)
      return;
    if (S[a] > S[b])
      swap(a, b);
    parent[a] = b;
    S[b] += S[a];
  }
  int size(int a) { return S[Find(a)]; }
  bool Connected(int a, int b) { return Find(a) == Find(b); }
};

using pii = pair<int, int>;

using ld = float;

ld calculateDistance(pii a, pii b) {
  return sqrt(pow((ld)b.first - (ld)a.first, 2) +
              pow((ld)b.second - (ld)a.second, 2));
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;

  vector<pii> cords(n + 1);
  vector<pair<ld, pair<pii, pii>>> distances;
  map<int, map<int, int>> nodesIds;

  for (int i = 1; i <= n; i++) {
    int a, b;
    cin >> a >> b;
    cords[i] = {a, b};
    nodesIds[a][b] = i;
  }

  UnionFind DSU(n + 1);

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j)
        continue;

      pii a = cords[i];
      pii b = cords[j];

      ld distance = calculateDistance(a, b);

      distances.push_back({distance, {a, b}});
    }
  }

  ld maxDistance = -1;

  sort(distances.begin(), distances.end());

  for (auto d : distances) {
    pii a = d.second.first;
    pii b = d.second.second;

    int aId = nodesIds[a.first][a.second];
    int bId = nodesIds[b.first][b.second];

    if (DSU.Connected(aId, bId))
      continue;

    DSU.Union(aId, bId);
    maxDistance = max(maxDistance, d.first);

    if (DSU.size(aId) >= n)
      break;
  }

  float radius = (float)maxDistance / 2;

  cout << fixed << setprecision(7) << radius << "\n";
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 612 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 58 ms 6092 KB Output is correct
7 Correct 61 ms 7124 KB Output is correct
8 Correct 137 ms 21992 KB Output is correct
9 Correct 126 ms 21968 KB Output is correct
10 Correct 140 ms 22736 KB Output is correct