oj.uz

Submission #474155

# Submission time Handle Problem Language Result Execution time Memory
474155 2021-09-17T03:03:18 Z Tuanchim Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 120 ms 12728 KB 
# include <bits/stdc++.h>
#define ll long long
#define fi freopen("orasiljaci.inp","r",stdin);
#define fo freopen("orasiljaci.out","w",stdout);
using namespace std;
struct kieurulieu { ll r,a,b; };
struct point { ll x,y; };
int cam[100005],n;
vector<kieurulieu>v;
point p[10005];
ll kq;
ll abs(point a, point b)
{
    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int find_cam(int x)
{
    if (cam[x]==x) return x;
    return cam[x]=find_cam(cam[x]);
}
bool cmp(kieurulieu a, kieurulieu b)
{
    return a.r<b.r;
}
int main ()
{
    //fi; fo;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cam[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);
    for (int i=0;i<v.size();i++){
        if (find_cam(v[i].a)!=find_cam(v[i].b))
        {
            kq=v[i].r;
            cam[find_cam(v[i].b)]=cam[find_cam(v[i].a)];
        }
    }
    cout<<fixed<<setprecision(7)<<sqrt(kq)/2;
}

Compilation message

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<kieurulieu>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     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 0 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 1 ms 588 KB Output is correct
6 Correct 22 ms 3520 KB Output is correct
7 Correct 23 ms 3520 KB Output is correct
8 Correct 57 ms 12664 KB Output is correct
9 Correct 119 ms 12728 KB Output is correct
10 Correct 120 ms 12728 KB Output is correct