256272026-02-23 18:24:48GeneratrollMobilNet (50 pont)cpp17Elfogadva 50/5035ms2668 KiB
#include <bits/stdc++.h>

using namespace std;

struct P {
	int x, y, id;
};

struct E {
	int u, v, w;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<P> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i].x >> v[i].y;
		v[i].id = i;
	}

	vector<E> e;
	e.reserve(2 * n);

	sort(v.begin(), v.end(), [](const P& a, const P& b) {
		if (a.x != b.x) return a.x < b.x;
		return a.y < b.y;
	});

	for (int i = 0; i < n - 1; i++) {
		if (v[i].x == v[i + 1].x) {
			e.push_back({v[i].id, v[i + 1].id, v[i + 1].y - v[i].y});
		}
	}

	sort(v.begin(), v.end(), [](const P& a, const P& b) {
		if (a.y != b.y) return a.y < b.y;
		return a.x < b.x;
	});

	for (int i = 0; i < n - 1; i++) {
		if (v[i].y == v[i + 1].y) {
			e.push_back({v[i].id, v[i + 1].id, v[i + 1].x - v[i].x});
		}
	}

	sort(e.begin(), e.end(), [](const E& a, const E& b) {
		return a.w < b.w;
	});

	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		p[i] = i;
	}

	auto find = [&](auto self, int i) -> int {
		if (p[i] == i) return i;
		return p[i] = self(self, p[i]);
	};

	auto unite = [&](int i, int j) {
		int r1 = find(find, i);
		int r2 = find(find, j);
		if (r1 != r2) {
			p[r1] = r2;
			return true;
		}
		return false;
	};

	int t = 0;
	int k = 0;
	int c = 0;

	for (const auto& edge : e) {
		if (unite(edge.u, edge.v)) {
			if (edge.w > t) {
				t = edge.w;
				k = 1;
			} else if (edge.w == t) {
				k++;
			}
			c++;
			if (c == n - 1) break;
		}
	}

	cout << t << '\n' << k << endl;

	return 0;
}

RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms508 KiB
2Elfogadva0/04ms564 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms508 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/21ms316 KiB
9Elfogadva2/22ms472 KiB
10Elfogadva2/23ms696 KiB
11Elfogadva2/23ms316 KiB
12Elfogadva2/24ms564 KiB
13Elfogadva3/37ms564 KiB
14Elfogadva3/312ms820 KiB
15Elfogadva3/314ms988 KiB
16Elfogadva3/317ms1288 KiB
17Elfogadva3/325ms1396 KiB
18Elfogadva3/324ms1924 KiB
19Elfogadva3/329ms2096 KiB
20Elfogadva3/335ms2668 KiB
21Elfogadva3/335ms2124 KiB
22Elfogadva3/332ms2140 KiB