# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
854459 | 2023-09-27T16:57:41 Z | vjudge1 | Odašiljači (COCI20_odasiljaci) | C++17 | 57 ms | 14800 KB |
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,O3,unroll-loops") #define int long long #define vi vector<int> #define vvi vector<vi> #define pii pair<int, int> #define vpi vector<pii> #define vvpi vector<vpi> #define vb vector<bool> #define vvb vector<vb> #define endl "\n" #define sp << " " << #define F(i, s, n) for(int i = s; i < n; i++) #define pb push_back #define fi first #define se second int mod = 998244353; int inf = LLONG_MAX >> 3; int mult(int x, int y) { return (x%mod)*(y%mod)%mod; } const int N = 1001; vi dad(N); int find(int x) { if(x == dad[x]) return x; return dad[x] = find(dad[x]); } void unite(int x, int y) { dad[find(x)] = find(y); } void solve() { int n; cin >> n; F(i, 0, n) dad[i] = i; vpi ant; vector<pair<double, pii>> edges; F(i, 0, n) { int x, y; cin >> x >> y; F(j, 0, ant.size()) { pii a = ant[j]; edges.pb({sqrtl((x-a.fi)*(x-a.fi) + (y-a.se)*(y-a.se)), {i, j}}); } ant.pb({x,y}); } sort(edges.begin(), edges.end()); double ans = 0; F(i, 0, edges.size()) { if(find(edges[i].se.fi) != find(edges[i].se.se)) { unite(edges[i].se.fi, edges[i].se.se); ans = edges[i].fi; } } cout << setprecision(12) << ans/2 << endl; } void setIO() { ios::sync_with_stdio(0); cin.tie(0); #ifdef Local freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif } signed main() { setIO(); int t = 1; //cin >> t; while(t--) solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 600 KB | Output is correct |
5 | Correct | 1 ms | 604 KB | Output is correct |
6 | Correct | 17 ms | 3544 KB | Output is correct |
7 | Correct | 17 ms | 4312 KB | Output is correct |
8 | Correct | 37 ms | 13776 KB | Output is correct |
9 | Correct | 56 ms | 13516 KB | Output is correct |
10 | Correct | 57 ms | 14800 KB | Output is correct |