63462023-11-21 21:00:39gergomiszoriMobilNet (50 pont)cpp17Elfogadva 50/5068ms22144 KiB
#include <bits/stdc++.h>

using namespace std;
 
#define ll long long
#define endl "\n"
#define pll pair<ll,ll>
#define fs first
#define sc second

ll find_set(ll v, vector<ll> &parent) 
{
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v], parent);
}

bool union_set(ll a, ll b, vector<ll> &parent)
{
    a = find_set(a, parent);
    b = find_set(b, parent);
    if (a == b) return false;
    parent[b] = a;
    return true;
}

void solve()
{
    ll n;
    cin >> n;

    vector<ll> parent(n);
    for(ll i = 0; i < n; i++) parent[i] = i;

    map<ll,vector<pll>> h, v;

    for(ll i = 0; i < n; i++)
    {
        ll a, b;
        cin >> a >> b;
        h[a].push_back({b, i}),
        v[b].push_back({a, i});
    }

    for(auto &i : h)
    {
        sort(i.sc.begin(), i.sc.end());
    }
    for(auto &i : v)
    {
        sort(i.sc.begin(), i.sc.end());
    }

    vector<pair<ll, pll>> g;

    for(auto &i : h)
    {
        for(ll j = 0; j < i.sc.size()-1; j++)
        {
            g.push_back({i.sc[j+1].fs-i.sc[j].fs, {i.sc[j+1].sc, i.sc[j].sc}});
            //cout << i.sc[j+1].fs-i.sc[j].fs << " " << i.sc[j+1].sc << " " << i.sc[j].sc << endl;
        }
    }
    for(auto &i : v)
    {
        for(ll j = 0; j < i.sc.size()-1; j++)
        {
            g.push_back({i.sc[j+1].fs-i.sc[j].fs, {i.sc[j+1].sc, i.sc[j].sc}});
            //cout << i.sc[j+1].fs-i.sc[j].fs << " " << i.sc[j+1].sc << " " << i.sc[j].sc << endl;
        }
    }
    
    ll ans = 0;
    ll ans2 = 1;

    sort(g.begin(), g.end());

    for(ll i = 0; i < g.size(); i++)
    {
        if(union_set(g[i].sc.fs, g[i].sc.sc, parent)) 
        {
            if(ans == g[i].fs) ans2++;
            else ans2 = 1;
            ans = g[i].fs;
        }
    }

    cout << ans << endl << ans2 << endl;
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1896 KiB
2Elfogadva0/08ms3736 KiB
3Elfogadva2/23ms2452 KiB
4Elfogadva2/23ms2820 KiB
5Elfogadva2/23ms2764 KiB
6Elfogadva2/23ms3160 KiB
7Elfogadva2/23ms3484 KiB
8Elfogadva2/23ms3876 KiB
9Elfogadva2/24ms4364 KiB
10Elfogadva2/24ms4852 KiB
11Elfogadva2/27ms5756 KiB
12Elfogadva2/29ms6376 KiB
13Elfogadva3/316ms7972 KiB
14Elfogadva3/319ms9328 KiB
15Elfogadva3/328ms11804 KiB
16Elfogadva3/332ms13136 KiB
17Elfogadva3/345ms16060 KiB
18Elfogadva3/337ms15440 KiB
19Elfogadva3/350ms18084 KiB
20Elfogadva3/357ms17768 KiB
21Elfogadva3/368ms22132 KiB
22Elfogadva3/364ms22144 KiB