4022 | 2023. 03. 09 09:45:54 | gortomi | MobilNet (50 pont) | cpp17 | Elfogadva 50/50 | 61ms | 16732 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<int> p, r;
struct edge
{
int l, r, val;
};
bool comp(edge a, edge b)
{
return a.val < b.val;
}
int get(int n)
{
return p[n] == 0 ? n : p[n] = get(p[n]);
}
void unio(int a, int b)
{
a = get(a);
b = get(b);
if(a != b)
{
if(r[b] > r[a]) swap(a, b);
p[b] = a;
if(r[b] == r[a]) r[a]++;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
p.resize(n + 1);
r.resize(n + 1);
map<int, vector<pair<int, int> > > x, y;
for(int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
x[a].push_back({b, i});
y[b].push_back({a, i});
}
vector<edge> e;
for(auto a : x)
{
vector<pair<int, int> > v = a.second;
sort(v.begin(), v.end());
for(int i = 0; i < v.size() - 1; i++)
{
edge b = {v[i].second, v[i + 1].second, v[i + 1].first - v[i].first};
e.push_back(b);
}
}
for(auto a : y)
{
vector<pair<int, int> > v = a.second;
sort(v.begin(), v.end());
for(int i = 0; i < v.size() - 1; i++)
{
edge b = {v[i].second, v[i + 1].second, v[i + 1].first - v[i].first};
e.push_back(b);
}
}
sort(e.begin(), e.end(), comp);
int maxi = 0, maxp = 0;
int k = n;
for(auto a : e)
{
if(a.val > maxi)
{
maxp = 0;
maxi = a.val;
}
if(get(a.l) != get(a.r))
{
unio(a.l, a.r);
maxp++;
k--;
if(k == 1)
{
break;
}
}
}
cout << maxi << "\n" << maxp;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1892 KiB | |||
2 | Elfogadva | 0/0 | 7ms | 3276 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2340 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2668 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2736 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 3124 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3368 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 3776 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 4116 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 4516 KiB | |||
11 | Elfogadva | 2/2 | 6ms | 4952 KiB | |||
12 | Elfogadva | 2/2 | 9ms | 5672 KiB | |||
13 | Elfogadva | 3/3 | 14ms | 6612 KiB | |||
14 | Elfogadva | 3/3 | 18ms | 7240 KiB | |||
15 | Elfogadva | 3/3 | 27ms | 9768 KiB | |||
16 | Elfogadva | 3/3 | 29ms | 9852 KiB | |||
17 | Elfogadva | 3/3 | 41ms | 12876 KiB | |||
18 | Elfogadva | 3/3 | 28ms | 10068 KiB | |||
19 | Elfogadva | 3/3 | 43ms | 12688 KiB | |||
20 | Elfogadva | 3/3 | 43ms | 11716 KiB | |||
21 | Elfogadva | 3/3 | 61ms | 16732 KiB | |||
22 | Elfogadva | 3/3 | 57ms | 16584 KiB |