6271 2023. 11. 10 21:37:03 Catt MobilNet (50 pont) cpp17 Elfogadva 50/50 104ms 18684 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;

vector<vector<pair<int, int> > > g;

vector<int> p;
vector<int> s;

int holvan(int x) {
    if(p[x] == x) return x;
    return p[x] = holvan(p[x]);
}

bool unio(int a, int b) {
    a = holvan(a);
    b = holvan(b);
    if(a == b) return false;

    if(s[a] < s[b]) swap(a, b);

    p[b] = a;
    s[a] += s[b];
    return true;
}

int main() {  
    int n; cin >> n;
    g.resize(n+1);
    p.resize(n+1);
    s.resize(n+1);

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


    map<int, vector<pair<int, int> > > x_ind, y_ind;
    for(int i = 0; i < n; i++) {
        int x,y;
        cin >> x >> y;
        x_ind[x].push_back({y, i});
        y_ind[y].push_back({x, i});
    }
    vector<pair<int, pair<int, int> > > elek;
    for(auto i : x_ind) {
        sort(i.second.begin(), i.second.end());
        for(int j = 0; j < i.second.size()-1; j++) {
            elek.push_back({i.second[j+1].first- i.second[j].first, {i.second[j].second, i.second[j+1].second}});
            //g[i.second[j].second].push_back({i.second[j+1].second, i.second[j+1].first- i.second[j].first});
            //g[i.second[j+1].second].push_back({i.second[j].second, i.second[j+1].first- i.second[j].first});
        }
    }
    for(auto i : y_ind) {
        sort(i.second.begin(), i.second.end());
        for(int j = 0; j < i.second.size()-1; j++) {
            elek.push_back({i.second[j+1].first- i.second[j].first, {i.second[j].second, i.second[j+1].second}});
            //g[i.second[j].second].push_back({i.second[j+1].second, i.second[j+1].first- i.second[j].first});
            //g[i.second[j+1].second].push_back({i.second[j].second, i.second[j+1].first- i.second[j].first});
        }
    }

    int maxj = 0, cnt = 0;

    sort(elek.begin(), elek.end());
    for(auto i : elek) {
        if(unio(i.second.first, i.second.second)) {
            if(maxj != i.first) cnt = 1;
            else cnt++;
            maxj = i.first;
        }
    }

    cout << maxj << " " << cnt;
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1872 KiB
2 Elfogadva 0/0 9ms 3460 KiB
3 Elfogadva 2/2 3ms 2292 KiB
4 Elfogadva 2/2 3ms 2536 KiB
5 Elfogadva 2/2 3ms 2724 KiB
6 Elfogadva 2/2 3ms 2860 KiB
7 Elfogadva 2/2 3ms 3144 KiB
8 Elfogadva 2/2 4ms 3356 KiB
9 Elfogadva 2/2 4ms 3752 KiB
10 Elfogadva 2/2 7ms 4152 KiB
11 Elfogadva 2/2 9ms 4936 KiB
12 Elfogadva 2/2 14ms 5780 KiB
13 Elfogadva 3/3 23ms 6828 KiB
14 Elfogadva 3/3 32ms 7616 KiB
15 Elfogadva 3/3 43ms 10592 KiB
16 Elfogadva 3/3 50ms 11104 KiB
17 Elfogadva 3/3 71ms 14292 KiB
18 Elfogadva 3/3 61ms 11792 KiB
19 Elfogadva 3/3 79ms 14528 KiB
20 Elfogadva 3/3 92ms 13980 KiB
21 Elfogadva 3/3 104ms 18684 KiB
22 Elfogadva 3/3 97ms 18468 KiB