제출 #904257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
904257		vjudge1	Odašiljači (COCI20_odasiljaci)	C++17	35 / 70	542 ms	55436 KiB

odasiljaci

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


typedef long long ll;
vector<int> padre, sz; // padre y tamao, hay que inicializar el tamaño

int lider(int nodo){
	if(nodo == padre[nodo]) return nodo;
	return padre[nodo] = lider(padre[nodo]);
}
bool IsSameSet(int a, int b){ //revisa si a y b estanen una misma componente
	return lider(a) == lider(b);
}
void Union(int a, int b){ //une a con b
	a=lider(a);
	b=lider(b);
	if(a==b) return;
	if(sz[a] < sz[b]) swap(a,b);
	sz[a] += sz[b];
	padre[b] = a;
}
ll pit(ll k,ll t, ll ki,ll ti){
	ll kii = (k-ki)*(k-ki);
	ll tii = (t-ti)*(t-ti);
	return kii + tii;
}
int main() {
	int n;
	const int x = 0;
	const int y = 1;
	cin>> n;
	sz.assign(n,1);
	padre.resize(n);
	vector<vector<long long>>v(n, vector<long long>(2));

	for(int i = 0; i<n;i++){
			cin>> v[i][x] >> v[i][y];
			padre[i] = i;
	}
	vector<vector<ll>> nar(n*n, vector<ll>(3));
	int ii = 0;
	long double maxkrusk = 0;
	for (int i = 0;i<n;i++){
		for (int j = 0;j<n;j++){
			nar[ii][0] = pit(v[i][x],v[i][y], v[j][x], v[j][y] );
			nar[ii][1] = i;
			nar[ii][2] = j;
			//cout<< ar[ii]<<endl;
			//cerr << nar[ii][0] << '\n';
			ii++;
			
		}
	}
	//sort(ar.begin(), ar.end());
	sort(nar.begin(), nar.end()); // x i j
	for(int i = 0; i<n*n;i++){
			
			if (IsSameSet(nar[i][1], nar[i][2]))continue;
			Union(nar[i][1], nar[i][2]);
			maxkrusk = nar[i][0];
	
			
	}
	maxkrusk = sqrt(maxkrusk);
	maxkrusk /= 2;
	cout << maxkrusk << '\n';
	return 0;
}

• Subtask 1: 35 / 70