Submission #485374

#	Time	Username	Problem	Language	Result	Execution time	Memory
485374		alexdumitru	Odašiljači (COCI20_odasiljaci)	C++14	42 / 70	545 ms	3460 KiB

odasiljaci

#include <bits/stdc++.h>
#define a first
#define b second
using namespace std;
int i,n,j,nr,viz[1005];
long double rez,delta=0.000000000001;
pair<int, int> v[1005];
vector<vector<int> > g;
void dfs(int nod=1)
{
    nr++;
    viz[nod]=1;
    for(int i=0;i<g[nod].size();i++)
        if(!viz[g[nod][i]])
            dfs(g[nod][i]);
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i].a>>v[i].b;
    long double st=0,dr=1000000000;
    while(dr-st>delta)
    {
        long double m=(st+dr)/2;
        nr=0;
        g.clear();
        for(i=1;i<=n+1;i++)
        {
            viz[i]=0;
            g.push_back({});
        }
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
            {
                long double x=sqrt((v[i].a-v[j].a)*(v[i].a-v[j].a)+(v[i].b-v[j].b)*(v[i].b-v[j].b));
                if(x<=m*2)
                {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        dfs();
        if(nr==n)
        {
            rez=m;
            dr=m;
        }
        else st=m;

    }
    cout<<fixed<<setprecision(7)<<rez;
    return 0;
}

Compilation message (stderr)

odasiljaci.cpp: In function 'void dfs(int)':
odasiljaci.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<g[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~

• Subtask 1: 42 / 70