oj.uz

Submission #374280

# Submission time Handle Problem Language Result Execution time Memory
374280 2021-03-07T06:40:54 Z ne4eHbKa Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 67 ms 8800 KB 
#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 1e3 + 5;

int p[N];
int get(int i) {return p[i] == i ? i : p[i] = get(p[i]);}
int unite(int i, int j) {p[i = get(i)] = j = get(j); return i != j;}

vector<pair<ll, pii>> e;

void solve() {
    int n;
    cin >> n;
    if(n == 1) return void(cout << "0\n");
    int x[n], y[n];
    for(int i = 0; i < n; ++i) cin >> x[i] >> y[i];
    auto sq = [] (const ll f) {return f * f;};
    e.clear();
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < i; ++j)
            e.push_back({sq(x[i] - x[j]) + sq(y[i] - y[j]), {i, j}});
    sort(bnd(e));
    iota(p, p + n, 0);
    int cnt = n - 1;
    for(auto &i : e)
        if(!(cnt -= unite(i.sd.ft, i.sd.sd)))
            return void(cout << sqrt(ld(i.ft)) / 2 << endl);
}

signed main() {
    cout.precision(8); cout << fixed;
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 18 ms 2536 KB Output is correct
7 Correct 18 ms 2536 KB Output is correct
8 Correct 43 ms 8672 KB Output is correct
9 Correct 67 ms 8672 KB Output is correct
10 Correct 65 ms 8800 KB Output is correct