oj.uz

Submission #356513

# Submission time Handle Problem Language Result Execution time Memory
356513 2021-01-23T12:34:41 Z PotatoOnABus Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 88 ms 8684 KB 
#include <bits/stdc++.h>
#include<iostream>
#include<vector>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
typedef long long ll;
typedef pair<double, double> par;
typedef pair<double, pair<int, int>> connec;
const int maxn = INT_MAX; 

vector<par> points;
vector<connec> vert;


double dist(pair <double, double> x, pair<double, double> y) {
	return sqrt((x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second));
}

vector<int> parovi;

int find(int x) {
	if (x == parovi[x]) return parovi[x];
	return parovi[x] = find(parovi[x]);
}

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	par tmp;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp.first >> tmp.second;
		points.push_back(tmp);
	}

	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			if (i == j) continue;
			connec temp;
			temp.second.first = i;
			temp.second.second = j;
			temp.first = dist(points[i], points[j]);
			vert.push_back(temp);
		}
	}
	
	sort(vert.begin(), vert.end());
	
	for (int i = 0; i < n; i++) parovi.push_back(i);

	double ans = 0.0;
	for (int i = 0; i < vert.size(); i++) {
		if (_union(vert[i].second.first, vert[i].second.second)) ans = vert[i].first / 2;
	}
	printf("%.9f \n", ans);
}

Compilation message

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:67: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]
   67 |  for (int i = 0; i < vert.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 23 ms 2540 KB Output is correct
7 Correct 21 ms 2540 KB Output is correct
8 Correct 54 ms 8684 KB Output is correct
9 Correct 79 ms 8684 KB Output is correct
10 Correct 88 ms 8684 KB Output is correct