oj.uz

Submission #356522

# Submission time Handle Problem Language Result Execution time Memory
356522 2021-01-23T12:45:00 Z dogav Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 659 ms 47420 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1001;

struct edge {
	double x;
	double y;
	int id;
	
	edge(int id, int x, int y) {
		this->id = id;
		this->x = x;
		this->y = y;
	}
	
	bool operator<(const edge a) const {
		return true;
	}
	
	string print() {
		return to_string(x) + " " + to_string(y);
	}
};

double dist(edge x, edge y) {
	return sqrt((x.x - y.x)*(x.x - y.x) + (x.y - y.y)*(x.y - y.y));
}

int par[MAXN];

int Find(int x) {
	if (x == par[x]) return par[x];
	return par[x] = Find(par[x]);
}
bool Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x != y) {
		par[x] = y;
		return true;
	}
	return false;
}



int main() {
	
	int n;
	cin >> n;
	
	vector<edge> edgevi;
	set< pair <double, pair< edge, edge > > >s;
	
	for (int i = 0; i < n; i++) {
		par[i] = i;
		int x,y;
		cin >> x >> y;
		edgevi.push_back(edge(i,x,y));
		for (int j = 0; j < i; j++) {
			edge e = edge(i,x,y);
			double udaljenost = dist(e, edgevi[j]);
			s.insert({udaljenost, {e, edgevi[j]}});
		}
	}
	
	double output = 0;
	for (auto it = s.begin(); it != s.end(); it++) {
		pair<double, pair<edge, edge>> p = (*it);
		if (Union(p.second.first.id, p.second.second.id)) {
			output = p.first / 2;
		}
	}
	printf("%.07f", output);
	
}

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 492 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 96 ms 12012 KB Output is correct
7 Correct 118 ms 12012 KB Output is correct
8 Correct 302 ms 26868 KB Output is correct
9 Correct 625 ms 47340 KB Output is correct
10 Correct 659 ms 47420 KB Output is correct