237892026-01-29 17:44:03algoproMobilNet (50 pont)cpp17Elfogadva 50/50259ms6540 KiB
// UUID: 479697b1-da01-46bb-a663-4bea98b05720
#include <bits/stdc++.h>
using namespace std;

vector<int> par;
int find(int X){
	if(par[X]==X) return X;
	return find(par[X]);
}

void onion(int A, int B){
	int pA=find(A), pB=find(B);
	if(pA==pB) return;
	par[pB]=pA;
}

int main() {
	int n; cin >> n;
	map<int, vector<array<int, 2>>> rowentries, colentries;
	vector<array<int, 2>> nodes(n); for(int i=0;i<n;i++){
		int x, y; cin >> x >> y;
		nodes[i]={x, y};
		rowentries[y].push_back({x, i});
		colentries[x].push_back({y, i});
	}
	vector<array<int, 3>> edges;
	for(auto [y, a] : rowentries){
		sort(a.begin(), a.end());
		for(int i=1;i<a.size();i++){
			edges.push_back({a[i][0]-a[i-1][0], a[i][1], a[i-1][1]});
		}
	}
	for(auto [x, a] : colentries){
		sort(a.begin(), a.end());
		for(int i=1;i<a.size();i++){
			edges.push_back({a[i][0]-a[i-1][0], a[i][1], a[i-1][1]});
		}
	}
	sort(edges.begin(), edges.end());
	par.resize(n);
	iota(par.begin(), par.end(), 0);
	int _max=0, maxCnt=0;
	for(auto [c, a, b] : edges){
		if(find(a)!=find(b)){
			onion(a, b);
			if(_max!=c){
				_max=c;
				maxCnt=0;
			}
			maxCnt++;
		}
	}
	cout << _max << '\n' << maxCnt;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/013ms820 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms388 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/22ms316 KiB
8Elfogadva2/22ms316 KiB
9Elfogadva2/24ms564 KiB
10Elfogadva2/26ms564 KiB
11Elfogadva2/28ms820 KiB
12Elfogadva2/214ms1424 KiB
13Elfogadva3/323ms1744 KiB
14Elfogadva3/350ms2132 KiB
15Elfogadva3/379ms3280 KiB
16Elfogadva3/367ms3380 KiB
17Elfogadva3/398ms4664 KiB
18Elfogadva3/382ms3444 KiB
19Elfogadva3/3259ms4524 KiB
20Elfogadva3/3120ms4028 KiB
21Elfogadva3/3166ms6532 KiB
22Elfogadva3/3158ms6540 KiB