Submission #1152272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152272		siewjh	Odašiljači (COCI20_odasiljaci)	C++20	70 / 70	95 ms	17000 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int MAXN = 1005;
int p[MAXN], sz[MAXN];
ll sq(ll v){
	return v * v;
}
ld dist(ll x1, ll y1, ll x2, ll y2){
	return sqrt((ld)(sq(x2 - x1) + sq(y2 - y1)));
}
int root(int x){
	if (p[x] == -1) return x;
	else return p[x] = root(p[x]);
}
int join(int ra, int rb){
	if (sz[ra] > sz[rb]) swap(ra, rb);
	p[ra] = rb;
	sz[rb] += sz[ra];
	return sz[rb];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int nums; cin >> nums;
	vector<pair<ll, ll>> pos(nums);
	for (int i = 0; i < nums; i++){
		ll x, y; cin >> x >> y;
		pos[i] = {x, y};
	}
	vector<tuple<ld, int, int>> elist;
	for (int i = 0; i < nums; i++)
		for (int j = 0; j < i; j++){
			ll x1, y1, x2, y2;
			tie(x1, y1) = pos[i]; tie(x2, y2) = pos[j];
			elist.push_back({dist(x1, y1, x2, y2), i, j});
		}
	sort(elist.begin(), elist.end());
	for (int i = 0; i < nums; i++){
		p[i] = -1; sz[i] = 1;
	}
	for (auto &[d, i, j] : elist){
		int ri = root(i), rj = root(j);
		if (ri == rj) continue;
		if (join(ri, rj) == nums){
			printf("%.7Lf", d / 2);
			break;
		}
	}
}

• Subtask 1: 70 / 70