Submission #904054

#	Time	Username	Problem	Language	Result	Execution time	Memory
904054		vjudge1	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	140 ms	22736 KiB

odasiljaci

#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 / 70