oj.uz

Submission #356497

# Submission time Handle Problem Language Result Execution time Memory
356497 2021-01-23T12:21:05 Z ivanpp Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 79 ms 8664 KB 
#include <bits/stdc++.h>

using namespace std;

int n;

int x[1005], y[1005];

int daddy[1005];

double ud(double x1, double x2, double y1, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int find(int a) {
	if (daddy[a] == a) return daddy[a];
	return daddy[a] = find(daddy[a]);
}

bool junion(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
		daddy[x] = y;
		return true;
	}
	return false;
}


int main() {
	
	cin >> n;
	
	vector < pair < double, pair <int, int> > > uds;
	
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
		
		for (int j = 0; j < i; j++) {
			uds.push_back({ud(x[j], x[i], y[j], y[i]), {i, j}});
		}
		
	}
	
	for (int i = 0; i < n; i++) {
		daddy[i] = i;
	}
	
	sort(uds.begin(), uds.end());
	
	double ans = 0.0;
	
	for (int i = 0; i < uds.size(); i++) {
		
		
		int xx = uds[i].second.first;
		int yy = uds[i].second.second;
		
		if (junion(xx, yy)) {
			ans = uds[i].first / 2;
		}
	}
	
	printf("%.9f \n", ans);

	
	return 0;
}

Compilation message

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:54:20: 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]
   54 |  for (int i = 0; i < uds.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 21 ms 2528 KB Output is correct
7 Correct 24 ms 2548 KB Output is correct
8 Correct 54 ms 8664 KB Output is correct
9 Correct 79 ms 8664 KB Output is correct
10 Correct 79 ms 8664 KB Output is correct