6163 2023. 11. 04 00:36:26 horvathabel MobilNet (50 pont) cpp17 Elfogadva 50/50 64ms 21400 KiB
#include <bits/stdc++.h>
using namespace std;
int cnt=0;
vector<int> p(100001,-1);
int maxw=0;
int ans=0;
struct node{
int a;
int b;
int w;
};
bool r(node a, node b){
return (a.w<b.w);
        }
int holvan(int a){
    if (p[a]==-1) return a;
    return p[a]=holvan(p[a]);
}
void unio(int a,int b, int w){
    a=holvan(a);
    b=holvan(b);
    if (a!=b){
        cnt++;
        if (w>maxw){
            maxw=w;
            ans=0;
        }
        if (w==maxw) ans++;
        p[b]=a;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    map<int,vector<pair<int,int>>> xk;
    map<int,vector<pair<int,int>>> yk;
    vector<node>  g;
    for (int i=0; i<n;i++){
        int x,y;
        cin>>x>>y;
        yk[y].push_back({x,i});
        xk[x].push_back({y,i});


    }
    for (auto a:xk){
        vector<pair<int,int>> lehetoseg=a.second;
        sort(lehetoseg.begin(),lehetoseg.end());
        for (int i=0; i<lehetoseg.size()-1;i++){
            int w=lehetoseg[i+1].first-lehetoseg[i].first;
            g.push_back({lehetoseg[i+1].second,lehetoseg[i].second,w});
        }
    }
    for (auto a:yk){
        vector<pair<int,int>> lehetoseg=yk[a.first];
        sort(lehetoseg.begin(),lehetoseg.end());
        for (int i=0; i<lehetoseg.size()-1;i++){
            int w=lehetoseg[i+1].first-lehetoseg[i].first;
            g.push_back({lehetoseg[i+1].second,lehetoseg[i].second,w});
        }
    }
    sort(g.begin(),g.end(),r);
    int i=0;
    while (cnt<n-1 && i<g.size()){
        unio(g[i].a,g[i].b,g[i].w);
        i++;
    }
    cout<<maxw<<"\n";
    cout<<ans;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 4ms 2700 KiB
2 Elfogadva 0/0 8ms 4192 KiB
3 Elfogadva 2/2 3ms 3356 KiB
4 Elfogadva 2/2 3ms 3472 KiB
5 Elfogadva 2/2 3ms 3480 KiB
6 Elfogadva 2/2 3ms 3596 KiB
7 Elfogadva 2/2 3ms 3808 KiB
8 Elfogadva 2/2 4ms 3892 KiB
9 Elfogadva 2/2 4ms 4284 KiB
10 Elfogadva 2/2 6ms 4956 KiB
11 Elfogadva 2/2 8ms 5288 KiB
12 Elfogadva 2/2 10ms 6028 KiB
13 Elfogadva 3/3 14ms 7112 KiB
14 Elfogadva 3/3 19ms 8116 KiB
15 Elfogadva 3/3 28ms 10904 KiB
16 Elfogadva 3/3 32ms 11728 KiB
17 Elfogadva 3/3 46ms 15068 KiB
18 Elfogadva 3/3 32ms 13300 KiB
19 Elfogadva 3/3 46ms 16268 KiB
20 Elfogadva 3/3 48ms 16188 KiB
21 Elfogadva 3/3 64ms 21400 KiB
22 Elfogadva 3/3 61ms 21292 KiB