oj.uz

답안 #391260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391260 2021-04-18T10:24:12 Z MrRobot_28 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 120 ms 16824 KB 
#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.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 29 ms 4536 KB Output is correct
7 Correct 29 ms 4544 KB Output is correct
8 Correct 72 ms 16820 KB Output is correct
9 Correct 120 ms 16824 KB Output is correct
10 Correct 119 ms 16824 KB Output is correct