oj.uz

Submission #356754

# Submission time Handle Problem Language Result Execution time Memory
356754 2021-01-23T15:28:02 Z hra_ved Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 82 ms 8664 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3+1;
int par[MAXN];
vector <pair <double, pair <int, int> > > vect;

int Find(int x);
bool UnionFind(int x, int y);

int main() {
    int N; cin>>N;
    for (unsigned i = 0; i < N; ++i) par[i] = i;
    double Xs[N+1], Ys[N+1];
    for (unsigned i=0; i<N; ++i) {
        cin>>Xs[i]>>Ys[i];
        for (int j = 0; j < i; j++) {
            double pit = sqrt( pow((Xs[i]- Xs[j]), 2) + pow((Ys[i]- Ys[j]), 2)) ;
            vect.push_back(make_pair(pit, make_pair(i, j)));
        }
    }
    sort(vect.begin(), vect.end());
    double rj = 0.0;
    for (unsigned i=0; i<vect.size(); ++i) {
        if (UnionFind(vect[i].second.first,vect[i].second.second)){
            rj = vect[i].first / 2;
        }
    }
    printf("%.9f\n", rj);
}

int Find(int x) {
    return (x == par[x]) ? x : par[x] = Find(par[x]);
}
bool UnionFind(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {par[x] = y; return true;}
    return false;
}

Compilation message

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:13:28: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   13 |     for (unsigned i = 0; i < N; ++i) par[i] = i;
      |                          ~~^~~
odasiljaci.cpp:15:25: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   15 |     for (unsigned i=0; i<N; ++i) {
      |                        ~^~
odasiljaci.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   17 |         for (int j = 0; j < i; j++) {
      |                         ~~^~~

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 23 ms 2528 KB Output is correct
7 Correct 21 ms 2548 KB Output is correct
8 Correct 58 ms 8664 KB Output is correct
9 Correct 78 ms 8664 KB Output is correct
10 Correct 82 ms 8664 KB Output is correct