61492023-11-03 22:24:54horvathabelMobilNet (50 pont)cpp17Időlimit túllépés 32/501.072s63140 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll cnt=0;
vector<ll> p(100001,-1);
vector<ll> siz(100001,0);
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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<pair<ll, ll>> z;
    for (int i=0; i<n;i++){
        ll x,y;
        cin>>x>>y;
        z.push_back({x,y});
        for (int j=i-1;j>=0;j--){
            if (z[i].first==z[j].first) g.push_back({i,j,abs(z[j].second-z[i].second)});
            if (z[i].second==z[j].second) g.push_back({i,j,abs(z[j].first-z[i].first)});
        }
    }
    sort(g.begin(),g.end(), r);
    ll i=0;
    while (cnt<n-1){
        unio(g[i].a,g[i].b,g[i].w);
        i++;
    }
    cout<<maxw<<"\n";
    cout<<ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/50
1Elfogadva0/04ms4788 KiB
2Elfogadva0/028ms7220 KiB
3Elfogadva2/24ms4984 KiB
4Elfogadva2/24ms5236 KiB
5Elfogadva2/24ms5452 KiB
6Elfogadva2/24ms5984 KiB
7Elfogadva2/24ms6072 KiB
8Elfogadva2/24ms6384 KiB
9Elfogadva2/28ms7204 KiB
10Elfogadva2/213ms7272 KiB
11Elfogadva2/223ms7460 KiB
12Elfogadva2/248ms8580 KiB
13Elfogadva3/3123ms10780 KiB
14Elfogadva3/3277ms21028 KiB
15Elfogadva3/3558ms33544 KiB
16Elfogadva3/3656ms22064 KiB
17Időlimit túllépés0/31.072s13856 KiB
18Futási hiba0/3354ms63140 KiB
19Időlimit túllépés0/31.067s31092 KiB
20Futási hiba0/3395ms62904 KiB
21Időlimit túllépés0/31.072s12540 KiB
22Időlimit túllépés0/31.041s18760 KiB