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

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;
    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++){
        int 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}});
        }

    }
    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);
    }
    cout<<maxw<<"\n";
    cout<<ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base44/50
1Elfogadva0/03ms2452 KiB
2Elfogadva0/014ms4072 KiB
3Elfogadva2/23ms3096 KiB
4Elfogadva2/23ms3416 KiB
5Elfogadva2/23ms3628 KiB
6Elfogadva2/23ms3876 KiB
7Elfogadva2/24ms3932 KiB
8Elfogadva2/24ms4268 KiB
9Elfogadva2/26ms5000 KiB
10Elfogadva2/28ms5144 KiB
11Elfogadva2/29ms5544 KiB
12Elfogadva2/214ms6628 KiB
13Elfogadva3/325ms8060 KiB
14Elfogadva3/354ms13304 KiB
15Elfogadva3/364ms21504 KiB
16Elfogadva3/364ms14768 KiB
17Elfogadva3/387ms17808 KiB
18Futási hiba0/3108ms62724 KiB
19Elfogadva3/3130ms33732 KiB
20Futási hiba0/3119ms62688 KiB
21Elfogadva3/3133ms23148 KiB
22Elfogadva3/3123ms23216 KiB