Submission #332550

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332550	2020-12-02T20:44:53 Z	souvenir_vayne	Odašiljači (COCI20_odasiljaci)	C++14	35 / 70	1000 ms	492 KB

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() {

    cin >> n;

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

    for(int tot = 0; tot < 32; tot++) {
        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

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

35.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	30 ms	492 KB	Output is correct
4	Correct	66 ms	384 KB	Output is correct
5	Correct	87 ms	436 KB	Output is correct
6	Execution timed out	1090 ms	364 KB	Time limit exceeded
7	Execution timed out	1093 ms	364 KB	Time limit exceeded
8	Execution timed out	1047 ms	364 KB	Time limit exceeded
9	Execution timed out	1048 ms	364 KB	Time limit exceeded
10	Execution timed out	1049 ms	364 KB	Time limit exceeded