255322026-02-20 15:35:32zeytonxMobilNet (50 pont)cpp17Elfogadva 50/50128ms14388 KiB
#include <bits/stdc++.h>

using namespace std;

vector<int> p, s;

int find_set(int a) {
    if (p[a] == a) return a;
    return p[a] = find_set(p[a]);
}

bool merge_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return false;
    if (s[b] > s[a]) swap(a, b);
    p[b] = a;
    s[a] += s[b];
    return true;
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(NULL);

    int n; cin >> n;
    map<int,set<pair<int,int>>> x, y;
    for (int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        x[a].emplace(b, i);
        y[b].emplace(a, i);
    }
    set<array<int,3>> g;
    for (auto i : x) {
        int last = -1;
        int last_i = -1;
        for (auto j : i.second) {
            if (last == -1) {
                last = j.first;
                last_i = j.second;
                continue;
            }
            g.insert({j.first-last, j.second, last_i});
            last = j.first; last_i = j.second;
        }
    }
    for (auto i : y) {
        int last = -1;
        int last_i = -1;
        for (auto j : i.second) {
            if (last == -1) {
                last = j.first;
                last_i = j.second;
                continue;
            }
            g.insert({j.first-last, j.second, last_i});
            last = j.first; last_i = j.second;
        }
    }
    p.resize(g.size()); s.resize(g.size(), 1);
    iota(p.begin(), p.end(), 0);

    int ans_min = 1e9;
    int ans_min_db = 0;
    int comp = g.size();
    for (auto i : g) {
        if (merge_set(i[1], i[2])) {
            if (ans_min == i[0]) ans_min_db++;
            else {
                ans_min = i[0];
                ans_min_db = 1;
            }
            comp--;
        }
        if (comp == 1) break;
    }

    cout << ans_min << endl << ans_min_db << endl;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms500 KiB
2Elfogadva0/08ms1596 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms508 KiB
7Elfogadva2/22ms448 KiB
8Elfogadva2/23ms572 KiB
9Elfogadva2/24ms824 KiB
10Elfogadva2/24ms1000 KiB
11Elfogadva2/27ms1392 KiB
12Elfogadva2/213ms2100 KiB
13Elfogadva3/323ms3372 KiB
14Elfogadva3/335ms4660 KiB
15Elfogadva3/354ms6812 KiB
16Elfogadva3/357ms7592 KiB
17Elfogadva3/390ms10020 KiB
18Elfogadva3/381ms9756 KiB
19Elfogadva3/3114ms12340 KiB
20Elfogadva3/3128ms14348 KiB
21Elfogadva3/3123ms14388 KiB
22Elfogadva3/3123ms13748 KiB