Submission #1152361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152361		Sandarach151	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	77 ms	17136 KiB

odasiljaci

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

#define int long long

vector<pair<long double, pair<int, int> > > vect;
vector<int> sze;
vector<int> lnk;

int find(int a){
	while(a!=lnk[a]){
		a = lnk[a];
	}
	return a;
}

bool same(int a, int b){
	return find(a)==find(b);
}

void unite(int a, int b){
	a = find(a);
	b = find(b);
	if(sze[a]<sze[b]){
		swap(a, b);
	}
	lnk[b]=a;
	sze[a]+=sze[b];
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	pair<long double, long double> points[n];
	sze.assign(n, 1);
	for(int i=0; i<n; i++){
		lnk.push_back(i);
	}
	for(int i=0; i<n; i++){
		long double a, b;
		cin >> a >> b;
		points[i] = make_pair(a, b);
	}
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			vect.push_back(make_pair(sqrt(pow(points[i].first-points[j].first, 2) + pow(points[i].second-points[j].second, 2)), make_pair(i, j)));
		}
	}
	sort(vect.begin(), vect.end());
	// for(int i=0; i<vect.size(); i++){
	// 	cout << vect[i].second.first << ' ' << vect[i].second.second << ' ' << vect[i].first << '\n';
	// }
	int cnt = 0;
	long double ans = 0;
	for(int i=0; i<vect.size(); i++){
		int a = vect[i].second.first;
		int b = vect[i].second.second;
		if(!same(a, b)){
			unite(a, b);
			cnt += 1;
			ans = vect[i].first / 2;
		}
		if(cnt==n-1) break;
	}
    printf("%.10Lf\n", ans);
    return 0;
}

• Subtask 1: 70 / 70