oj.uz

Submission #356365

# Submission time Handle Problem Language Result Execution time Memory
356365 2021-01-23T09:47:18 Z fbosnjak Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 80 ms 8792 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000;
int par[maxn];

double Dist(double a1, double b1, double a2, double b2) {
    return sqrt((a1 - a2)*(a1 - a2) + (b1 - b2)*(b1 - b2));
}
int Find(int x) {
    return (x == par[x]) ? x : par[x] = Find(par[x]);
}
bool Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {par[x] = y; return true;}
    return false;
}

int main() 
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) par[i] = i;
    double x[N], y[N];
    vector <pair <double, pair <int, int> > > v;
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        for (int j = 0; j < i; j++) {
            v.push_back(make_pair(Dist(x[i], y[i], x[j], y[j]), make_pair(i, j)));
        }
    }
    sort(v.begin(), v.end());
    double sol = 0.0;
    for (int i = 0; i < v.size(); i++) {
        int a = v[i].second.first;
        int b = v[i].second.second;

        if (Union(a, b)) sol = v[i].first / 2;
    }

    printf("%.9f\n", sol);
}

Compilation message

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 21 ms 2528 KB Output is correct
7 Correct 21 ms 2528 KB Output is correct
8 Correct 51 ms 8664 KB Output is correct
9 Correct 80 ms 8792 KB Output is correct
10 Correct 80 ms 8664 KB Output is correct