oj.uz

Submission #1094122

# Submission time Handle Problem Language Result Execution time Memory
1094122 2024-09-28T13:53:19 Z vjudge1 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 46 ms 8656 KB 
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

class DisjointSet {
private:

    mutable std::vector<int> root;

public:

    DisjointSet() {};

    DisjointSet(const int n): root(n, -1) {};

    virtual ~DisjointSet() {};

    void reload() {
        std::fill(root.begin(), root.end(), -1);
    };

    int getRoot(const int x) const {
        return root[x] < 0 ? x : (root[x] = getRoot(root[x]));
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (root[x] < root[y]) {
            root[x] += root[y];
            root[y] = x;
        } else {
            root[y] += root[x];
            root[x] = y;
        }
        return true;
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    int getTreeSize(const int x) const {
        return -root[getRoot(x)];
    }

};

constexpr int MAX_N = 1E3 + 3;

ll result;
int n, x[MAX_N], y[MAX_N];
vector<tuple<ll, int, int> > edges;

ll findSquare(const ll x) {
    return x * x;
}

signed main() {

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
//    freopen("output.OUT", "w", stdout);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cout.precision(9);
    cout.setf(ios::fixed, ios::floatfield);

    cin >> n;

    DisjointSet dsu(n);

    fore(i, 0, n) {
        cin >> x[i] >> y[i];
        fore(j, 0, i)
            edges.emplace_back(findSquare(x[i] - x[j]) + findSquare(y[i] - y[j]), j, i);
    }

    sort(all(edges));

    for (const auto &[l, i, j] : edges)
        if (dsu.unite(i, j))
            result = l;

    cout << sqrt(result) / 2 << '\n';

    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 13 ms 2516 KB Output is correct
7 Correct 12 ms 2624 KB Output is correct
8 Correct 36 ms 8648 KB Output is correct
9 Correct 41 ms 8656 KB Output is correct
10 Correct 46 ms 8652 KB Output is correct