61612023-11-04 00:21:11horvathabelMobilNet (50 pont)cpp17Futási hiba 44/50162ms62756 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=int;
ll cnt=0;
vector<ll> p(100001,-1);
ll maxw=0;
ll ans=0;


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++;
        p[b]=a;
    }
}

int main()
{
    int n;
    cin>>n;
    map<ll,vector<pair<ll,ll>>> xk;
    map<ll,vector<pair<ll,ll>>> yk;
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> g;
    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({abs(y-a.first),{i,a.second}});
        }
        for (pair<int,int> a:yk[y]){
            if (i!=a.second)  g.push({abs(x-a.first),{i,a.second}});
        }

    }
    ll i=0;
    while (cnt<n-1 && !g.empty()){
        pair<int,pair<int,int>> v=g.top();
        g.pop();
        unio(v.second.first,v.second.second,v.first);
        i++;
    }
    cout<<maxw<<"\n";
    cout<<ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base44/50
1Elfogadva0/03ms2452 KiB
2Elfogadva0/017ms4184 KiB
3Elfogadva2/23ms2896 KiB
4Elfogadva2/23ms3364 KiB
5Elfogadva2/23ms3448 KiB
6Elfogadva2/23ms4072 KiB
7Elfogadva2/24ms4000 KiB
8Elfogadva2/24ms4360 KiB
9Elfogadva2/27ms4892 KiB
10Elfogadva2/28ms4908 KiB
11Elfogadva2/213ms5232 KiB
12Elfogadva2/218ms6396 KiB
13Elfogadva3/330ms8112 KiB
14Elfogadva3/363ms13380 KiB
15Elfogadva3/379ms21924 KiB
16Elfogadva3/378ms15052 KiB
17Elfogadva3/3108ms17980 KiB
18Futási hiba0/3125ms62756 KiB
19Elfogadva3/3148ms33888 KiB
20Futási hiba0/3133ms62716 KiB
21Elfogadva3/3162ms23040 KiB
22Elfogadva3/3155ms23444 KiB