Submission #332552

#	Time	Username	Problem	Language	Result	Execution time	Memory
332552		souvenir_vayne	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	271 ms	492 KiB

odasiljaci

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <chrono>
#define pb push_back
#define INF 0x3f3f3f3f
//#define LINF 0x3f3f3f3f3f3f3f3f
//#define endl '\n'
#define ll long long
#define f first
#define int long long
#define fin cin
#define fout cout
#define s second
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cout << "DEBUG " << x << endl
#define debug2(x, y) cout << "DEBUG " << x << " " << y << endl
#define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl
#define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl
#define all(x) x.begin(), x.end()
#define left vadia
#define lb lower_bound
#define right puta
using namespace std;
using namespace __gnu_pbds;
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0);
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
typedef pair<ll, ll> pii;
typedef vector<vector<char>> mat;
typedef pair<int, string> pis;
const ll mod = 1e9+7;
typedef vector<int> vi;
typedef pair<int, pair<int, int>> piii;

pii v[1005];
int pai[1005], h[1005], n;

int find(int x) {
    if(pai[x] == x)
        return x;
    else return pai[x] = find(pai[x]);
}

void join(int a, int b) {
    a = find(a), b = find(b);
    if(a == b)
        return;
    if(h[a] == h[b]) {
        h[a]++;
        pai[b] = a;
        return;
    }

    if(h[a] < h[b])
        swap(a, b);
    pai[b] = a;
    return;
}

double dist(int a, int b) {
    double x = v[a].f - v[b].f;
    double y = v[a].s - v[b].s;
    return sqrt(x*x + y*y);
}

bool check(double mid) {

    mid /= 1e6;
    for(int i = 0; i < n; h[i] = 0, i++)
        pai[i] = i;

    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(  dist(i, j) <= 2.0*mid )
                join(i, j);

    for(int i = 1; i < n; i++)
        if(find(i) != find(0))
            return 0;

    return 1;

}

int32_t main() {

    FAST;
    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> v[i].f >> v[i].s;
    int ans = 2e16;

        int ini = 0, mid, end = 2e16;
        while(ini <= end) {
            mid = (ini+end)>>1;
            if(check(mid)) {
                end = mid-1;
                ans = min(ans, mid);
            }
            else
                ini = mid+1;
        }


    cout << fixed << setprecision(6) << (double)ans/1e6 << endl;



}

Compilation message (stderr)

odasiljaci.cpp: In function 'void setIO(std::string)':
odasiljaci.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
odasiljaci.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 70