oj.uz

Submission #768871

# Submission time Handle Problem Language Result Execution time Memory
768871 2023-06-28T19:47:28 Z MilosMilutinovic Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 52 ms 8640 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, x[N], y[N], rt[N];
struct Event {
    double r;
    int i, j;
    bool const operator < (const Event& ev) {
        return r < ev.r;
    }
};
int root(int x) { return rt[x] == x ? x : rt[x] = root(rt[x]); }
bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    rt[x] = y;
    return true;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &y[i]);
    }
    vector<Event> ev;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            double d = (x[i] - x[j]) * 1ll * (x[i] - x[j]) + (y[i] - y[j]) * 1ll * (y[i] - y[j]);
            d = sqrt(d) / 2;
            ev.push_back({d, i, j});
        }
    }
    sort(ev.begin(), ev.end());
    if (ev.empty()) {
        printf("0.000000");
        return 0;
    }
    int comps = n;
    for (int i = 1; i <= n; i++) {
        rt[i] = i;
    }
    for (auto& p : ev) {
        if (unite(p.i, p.j)) {
            comps--;
        }
        if (comps == 1) {
            printf("%.6lf", p.r);
            return 0;
        }
    }
    return 0;
}

Compilation message

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
odasiljaci.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d%d", &x[i], &y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 10 ms 2504 KB Output is correct
7 Correct 12 ms 2504 KB Output is correct
8 Correct 24 ms 8580 KB Output is correct
9 Correct 52 ms 8640 KB Output is correct
10 Correct 52 ms 8640 KB Output is correct