61582023-11-04 00:10:15horvathabelMobilNet (50 pont)cpp17Futási hiba 44/50270ms63032 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll cnt=0;
vector<ll> p;
vector<ll> siz;
ll maxw=0;
ll ans=0;
struct node{
    ll a;
    ll b;
    ll w;

};

ll holvan(ll a){
    if (p[a]==-1) return a;
    return p[a]=holvan(p[a]);
}
void unio(ll a,ll b, ll w){
    a=holvan(a);
    b=holvan(b);
    if (a!=b){
        cnt++;
        if (w>maxw){
            maxw=w;
            ans=0;
        }
        if (w==maxw) ans++;
        if (siz[a]>siz[b]){
            siz[a]++;
            p[b]=a;
            return;
        }
        siz[b]++;
        p[a]=b;
    }
}
vector<node> g;
bool r(node a, node b){
return (a.w<b.w) ;
}

int main()
{
    int n;
    cin>>n;
    p.resize(n+1,-1);
    siz.resize(n+1,1);
    map<ll,vector<pair<ll,ll>>> xk;
    map<ll,vector<pair<ll,ll>>> yk;

    for (int i=0; i<n;i++){
        ll x,y;
        cin>>x>>y;
        yk[y].push_back({x,i});
        xk[x].push_back({y,i});
        for (pair<int,int> a:xk[x]){
            if (i!=a.second) g.push_back({i,a.second,abs(y-a.first)});
        }
        for (pair<int,int> a:yk[y]){
            if (i!=a.second)  g.push_back({i,a.second,abs(x-a.first)});
        }

    }
    sort(g.begin(),g.end(), r);
    ll 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ÖsszpontTesztVerdiktIdőMemória
base44/50
1Elfogadva0/03ms1808 KiB
2Elfogadva0/016ms4388 KiB
3Elfogadva2/23ms2340 KiB
4Elfogadva2/23ms2452 KiB
5Elfogadva2/23ms2564 KiB
6Elfogadva2/23ms2900 KiB
7Elfogadva2/23ms3016 KiB
8Elfogadva2/24ms3384 KiB
9Elfogadva2/27ms4100 KiB
10Elfogadva2/28ms4324 KiB
11Elfogadva2/212ms5128 KiB
12Elfogadva2/218ms6348 KiB
13Elfogadva3/332ms9408 KiB
14Elfogadva3/357ms19400 KiB
15Elfogadva3/3155ms33188 KiB
16Elfogadva3/393ms21536 KiB
17Elfogadva3/3112ms24960 KiB
18Futási hiba0/386ms63032 KiB
19Elfogadva3/3270ms60392 KiB
20Futási hiba0/378ms62836 KiB
21Elfogadva3/3197ms37544 KiB
22Elfogadva3/3194ms37772 KiB