237882026-01-29 17:43:12algoproMobilNet (50 pont)cpp17Elfogadva 50/5043ms8244 KiB
// UUID: 8e29c463-c787-4519-8a1d-5e3945deff6c
#include <bits/stdc++.h>
using namespace std;

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

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        return true;
    }
};

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

    int n; cin >> n;

    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++)cin >> x[i] >> y[i];

    vector<Edge> e;
    unordered_map<int, vector<pair<int,int>>> byX;
    byX.reserve(n * 2);
    for (int i = 0; i < n; i++) {
        byX[x[i]].push_back({y[i], i});
    }
    for (auto &kv : byX) {
        auto &v = kv.second;
        sort(v.begin(), v.end());
        for (int i = 1; i < (int)v.size(); i++) {
            e.push_back({
                v[i-1].second,
                v[i].second,
                v[i].first - v[i-1].first
            });
        }
    }

    unordered_map<int, vector<pair<int,int>>> byY;
    byY.reserve(n * 2);
    for (int i = 0; i < n; i++) {
        byY[y[i]].push_back({x[i], i});
    }
    for (auto &kv : byY) {
        auto &v = kv.second;
        sort(v.begin(), v.end());
        for (int i = 1; i < (int)v.size(); i++) {
            e.push_back({
                v[i-1].second,
                v[i].second,
                v[i].first - v[i-1].first
            });
        }
    }

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

    DSU dsu(n);
    int T = 0;
    int K = 0;
    int used = 0;

    for (auto &e : e) {
        if (dsu.unite(e.u, e.v)) {
            used++;
            if (e.w > T) {
                T = e.w;
                K = 1;
            } else if (e.w == T) {
                K++;
            }
            if (used == n - 1) break;
        }
    }

    cout << T << "\n" << K << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/04ms1076 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/21ms368 KiB
8Elfogadva2/22ms776 KiB
9Elfogadva2/23ms760 KiB
10Elfogadva2/24ms820 KiB
11Elfogadva2/24ms820 KiB
12Elfogadva2/28ms1588 KiB
13Elfogadva3/39ms2160 KiB
14Elfogadva3/314ms2360 KiB
15Elfogadva3/320ms3924 KiB
16Elfogadva3/323ms3760 KiB
17Elfogadva3/332ms5276 KiB
18Elfogadva3/325ms4488 KiB
19Elfogadva3/335ms6572 KiB
20Elfogadva3/337ms6800 KiB
21Elfogadva3/343ms8244 KiB
22Elfogadva3/341ms7028 KiB