61472023-11-03 22:12:39horvathabelMobilNet (50 pont)cpp17Time limit exceeded 5/501.1s9716 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) ;
    }
ll tav(ll x1, ll y1, ll x2, ll y2){
return (abs(x1-x2)+abs(y1-y2));
}

int main()
{
    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--){
            g.push_back({i,j,tav(x,y,z[j].first,z[j].second)});
        }
        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;
}
SubtaskSumTestVerdictTimeMemory
base5/50
1Accepted0/04ms4788 KiB
2Time limit exceeded0/01.08s6268 KiB
3Partially correct1/28ms5748 KiB
4Partially correct1/263ms6708 KiB
5Accepted2/28ms6048 KiB
6Partially correct1/2662ms9252 KiB
7Time limit exceeded0/21.052s7124 KiB
8Time limit exceeded0/21.057s5892 KiB
9Time limit exceeded0/21.074s7420 KiB
10Time limit exceeded0/21.065s7764 KiB
11Time limit exceeded0/21.037s6212 KiB
12Time limit exceeded0/21.07s6368 KiB
13Time limit exceeded0/31.065s8236 KiB
14Time limit exceeded0/31.044s8476 KiB
15Time limit exceeded0/31.065s7132 KiB
16Time limit exceeded0/31.074s8972 KiB
17Time limit exceeded0/31.1s9080 KiB
18Time limit exceeded0/31.074s9332 KiB
19Time limit exceeded0/31.074s9568 KiB
20Time limit exceeded0/31.069s9708 KiB
21Time limit exceeded0/31.057s9716 KiB
22Time limit exceeded0/31.049s9528 KiB