Submission #391260

#	Time	Username	Problem	Language	Result	Execution time	Memory
391260		MrRobot_28	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	120 ms	16824 KiB

odasiljaci

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define ll long long
#define ld long double
const int N = 3e5 + 100;
ld dist(ll x, ll y, ll x1, ll y1)
{
    return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}
int dsu[N], rang[N];
int pred(int a)
{
    if(a == dsu[a]) return a;
    return dsu[a] = pred(dsu[a]);
}
void unite(int a, int b)
{
    a = pred(a);
    b = pred(b);
    if(rang[a] > rang[b])
    {
        swap(a, b);
    }
    dsu[b] = a;
    if(rang[a] == rang[b])
    {
        rang[a]++;
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> x(n), y(n);
    for(int i = 0; i < n; i++)
    {
        dsu[i] = i;
        rang[i] = 1;
        cin >> x[i] >> y[i];
    }
    vector <pair <ld, pair <int, int> > > mass;
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            mass.push_back({dist(x[i], y[i], x[j], y[j]), {i, j}});
        }
    }
    sort(mass.begin(), mass.end());
    int cnt = 0;
    for(int i = 0; i < sz(mass); i++)
    {
        if(pred(mass[i].Y.X) != pred(mass[i].Y.Y))
        {
            cnt++;
            if(cnt == n - 1)
            {
                cout << fixed << setprecision(10) << mass[i].X / 2;
                return 0;
            }
            unite(mass[i].Y.X, mass[i].Y.Y);
        }
    }
    return 0;
}

• Subtask 1: 70 / 70