62712023-11-10 21:37:03CattMobilNet (50 pont)cpp17Accepted 50/50104ms18684 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1872 KiB
2Accepted0/09ms3460 KiB
3Accepted2/23ms2292 KiB
4Accepted2/23ms2536 KiB
5Accepted2/23ms2724 KiB
6Accepted2/23ms2860 KiB
7Accepted2/23ms3144 KiB
8Accepted2/24ms3356 KiB
9Accepted2/24ms3752 KiB
10Accepted2/27ms4152 KiB
11Accepted2/29ms4936 KiB
12Accepted2/214ms5780 KiB
13Accepted3/323ms6828 KiB
14Accepted3/332ms7616 KiB
15Accepted3/343ms10592 KiB
16Accepted3/350ms11104 KiB
17Accepted3/371ms14292 KiB
18Accepted3/361ms11792 KiB
19Accepted3/379ms14528 KiB
20Accepted3/392ms13980 KiB
21Accepted3/3104ms18684 KiB
22Accepted3/397ms18468 KiB