Submission #375592

#	Time	Username	Problem	Language	Result	Execution time	Memory
375592		muhi1112	Odašiljači (COCI20_odasiljaci)	C++17	42 / 70	120 ms	16852 KiB

odasiljaci

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

#define f1 first
#define s2 second
#define INF 1e9+10
#define ll long long
#define pb push_back
#define fri(a) freopen(a,"r",stdin)
#define fro(a) freopen(a,"w",stdout)
const int N=2e5+5;

int n,a,b,p[N];
vector<pair<int,int>>v;
vector<pair<long double,pair<int,int>>>u;
long double ans;

long double calc(pair<int,int>x,pair<int,int>y){
	return sqrt(abs((x.f1-y.f1)*(x.f1-y.f1))+abs((x.s2-y.s2)*(x.s2-y.s2)));
}

int parent(int x){
	if(x==p[x])return x;
	return p[x]=parent(p[x]);;
}

long double dsu(pair<long double,pair<int,int>> pp){
	int x=pp.s2.f1;
	int y=pp.s2.s2;
	x=parent(x);
	y=parent(y);
	if(x!=y){
		p[x]=y;
		return pp.f1;
	}
	else return 0.0;
}

void solve(){
	cin>>n;
	for(int i=0;i<n;i++){
		p[i]=i;
		cin>>a>>b;
		v.pb({a,b});
		for(int j=i-1;j>=0;j--){
			u.pb({calc(v[i],v[j]),{i,j}});
		}
	}
	sort(u.begin(),u.end());
	for(int i=0;i<u.size();i++){
		ans=max(ans,dsu(u[i]));
	}
	cout.precision(10);
	cout<<ans/2.0<<endl;


}

int main(){

	//fri("in.txt");
	//fro("out.txt");
	solve();

	return 0;
}

Compilation message (stderr)

odasiljaci.cpp: In function 'void solve()':
odasiljaci.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<u.size();i++){
      |              ~^~~~~~~~~

• Subtask 1: 42 / 70