oj.uz

Submission #474140

# Submission time Handle Problem Language Result Execution time Memory
474140 2021-09-17T02:11:10 Z LeeRise Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 121 ms 12728 KB 
# include <bits/stdc++.h>
# define auto_ac int main
using namespace std;
struct HA{
    long long d,a,b;
};
struct point
{
    long long x,y;
};
int n;
int root[100005];
vector<HA>v;
point p[10005];
long long abs(point a, point b)
{
    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int find_root(int x)
{
    if (root[x]==x) return x;
    return root[x]=find_root(root[x]);
}
bool cmp(HA a, HA b)
{
    return a.d<b.d;
}
auto_ac()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++){
        root[i]=i;
        cin>>p[i].x>>p[i].y;
        for (int j=1;j<i;j++){
                v.push_back({abs(p[j],p[i]),j,i});
        }
    }
    sort (v.begin(),v.end(),cmp);
    long long ans;
    for (int i=0;i<v.size();i++){
        if (find_root(v[i].a)!=find_root(v[i].b)){
            ans=v[i].d;
            root[find_root(v[i].b)]=root[find_root(v[i].a)];
        }
    }
    cout<<fixed<<setprecision(7)<<sqrt(ans)/2;
}

Compilation message

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

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory 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 588 KB Output is correct
6 Correct 25 ms 3520 KB Output is correct
7 Correct 24 ms 3520 KB Output is correct
8 Correct 56 ms 12728 KB Output is correct
9 Correct 121 ms 12728 KB Output is correct
10 Correct 121 ms 12728 KB Output is correct