oj.uz

Submission #334619

# Submission time Handle Problem Language Result Execution time Memory
334619 2020-12-09T15:08:33 Z GioChkhaidze Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 75 ms 8664 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N=1e3+1;

int n,p[N],sz[N];
double x[N],y[N];
vector < pair < double , pair < int , int > > > v;

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

main () {
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>x[i]>>y[i];
		p[i]=i,sz[i]=1;
	}
	
	for (int i=1; i<=n; i++)
		for (int j=1; j<i; j++)
			v.pb({sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))/2.0,{i,j}});
	
	sort(v.begin(),v.end());
	
	for (int i=0; i<v.size(); i++) {
		int a=v[i].S.F,b=v[i].S.S;
		if (P(a)==P(b)) continue;
		a=P(a),b=P(b);
		p[b]=a;
		sz[a]+=sz[b];
		sz[b]=0;
		if (sz[a]==n) {
			printf("%.7f",v[i].F);
			exit(0);
		}
	}	
}

Compilation message

odasiljaci.cpp:20:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main () {
      |       ^
odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i=0; i<v.size(); i++) {
      |                ~^~~~~~~~~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 20 ms 2528 KB Output is correct
7 Correct 20 ms 2528 KB Output is correct
8 Correct 48 ms 8664 KB Output is correct
9 Correct 74 ms 8664 KB Output is correct
10 Correct 75 ms 8664 KB Output is correct