oj.uz

Submission #807324

# Submission time Handle Problem Language Result Execution time Memory
807324 2023-08-04T16:00:23 Z Tunglam07 Odašiljači (COCI20_odasiljaci) C++17
42 / 70
 987 ms 320 KB 
#include<bits/stdc++.h>
using namespace std;

long long n, parent[1001], limit = 100;
double lt = 0, rt = 1e9;

pair<int, int> a[1001];
 
int findparent(int id)
{
	if(id == parent[id])
	{
		return id;
	}
	else	
	{
		return parent[id] = findparent(parent[id]);
	}
}
 
bool check(double id)
{
	for(int i = 1; i <= n; ++i)	
	{
		parent[i] = i;
	}
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
		{
			double temp = (a[i].first - a[j].first) * (a[i].first - a[j].first) + (a[i].second - a[j].second) * (a[i].second - a[j].second);
			if(sqrt(temp) < id * 2)
			{
				long long a = findparent(i), b = findparent(j);
				parent[a] = parent[b];
			}
		}
	}
	parent[1] = findparent(1);
	for(int i = 2; i <= n; ++i)	
	{
		if(findparent(i) != parent[1])	
		{
			return 0;
		}	
	}
	return 1;
}
 
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)	
	{
		cin >> a[i].first >> a[i].second;
	}
	while(lt < rt && limit--)
	{
		double mid = (lt + rt) / 2;
		if(!check(mid))	
		{
			lt = mid;
		}
		else	
		{
			rt = mid;
		}
	}
	cout << setprecision(7) << fixed << lt;
}

Subtask #1
42.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 4 ms 312 KB Output isn't correct
5 Incorrect 10 ms 300 KB Output isn't correct
6 Correct 94 ms 212 KB Output is correct
7 Correct 96 ms 296 KB Output is correct
8 Correct 202 ms 212 KB Output is correct
9 Incorrect 983 ms 320 KB Output isn't correct
10 Incorrect 987 ms 316 KB Output isn't correct