Submission #1152264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152264		gelastropod	Odašiljači (COCI20_odasiljaci)	C++20	35 / 70	274 ms	16796 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> tree;

int fin(int n) {
	if (tree[n] == n) return n;
	return tree[n] = fin(tree[n]);
}

void join(int a, int b) {
	a = fin(a);
	b = fin(b);
	if (a == b) return;
	tree[b] = a;
}

signed main() {
	int n, x, y;
	cin >> n;
	vector<pair<int, int>> coords;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		coords.push_back({ x, y });
	}
	priority_queue<pair<long double, pair<int, int>>, vector<pair<long double, pair<int, int>>>, greater<pair<long double, pair<int, int>>>> pq;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			pq.push({ pow((coords[i].first - coords[j].first) * (coords[i].first - coords[j].first) + (coords[i].second - coords[j].second) * (coords[i].second - coords[j].second), (long double)0.5), {i, j} });
	for (int i = 0; i < n; i++)
		tree.push_back(i);
	long double ans = -1;
	while (!pq.empty()) {
		if (fin(pq.top().second.first) != fin(pq.top().second.second)) {
			ans = max(ans, pq.top().first);
			join(pq.top().second.first, pq.top().second.second);
		}
		pq.pop();
	}
	cout << ans / 2 << '\n';
}

• Subtask 1: 35 / 70