7242 | 2024. 01. 05 10:22:56 | Error42 | Hírvivők csoportosítása (40) | cpp17 | Elfogadva 40/40 | 24ms | 6940 KiB |
#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
struct person {
int x, y;
};
vector<int> parent;
vector<int> sz;
int components;
int find(int const x) {
if (parent[x] == -1)
return x;
return parent[x] = find(parent[x]);
}
void merge(int const x, int const y) {
int px = find(x);
int py = find(y);
if (px == py)
return;
components--;
if (sz[px] < sz[py])
swap(px, py);
parent[py] = px;
sz[px] += sz[py];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, h, k;
cin >> n >> m >> h >> k;
vector<person> people(h);
for (person& p : people)
cin >> p.x >> p.y;
vector<pair<int, pair<int, int>>> distances;
for (int i = 0; i < h - 1; i++) {
for (int j = i + 1; j < h; j++) {
distances.push_back({ abs(people[i].x - people[j].x) + abs(people[i].y - people[j].y), { i, j } });
}
}
sort(distances.begin(), distances.end());
parent.assign(h, -1);
sz.assign(h, 1);
components = h;
if (components <= k) {
cout << "0\n";
return 0;
}
for (auto dist : distances) {
int const d = dist.first;
int const i = dist.second.first;
int const j = dist.second.second;
merge(i, j);
if (components <= k) {
cout << d << "\n";
return 0;
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 40/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1824 KiB | |||
2 | Elfogadva | 0/0 | 19ms | 5348 KiB | |||
3 | Elfogadva | 1/1 | 3ms | 2364 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2292 KiB | |||
5 | Elfogadva | 1/1 | 6ms | 3416 KiB | |||
6 | Elfogadva | 1/1 | 4ms | 3512 KiB | |||
7 | Elfogadva | 1/1 | 3ms | 3104 KiB | |||
8 | Elfogadva | 1/1 | 3ms | 3092 KiB | |||
9 | Elfogadva | 1/1 | 3ms | 3108 KiB | |||
10 | Elfogadva | 1/1 | 6ms | 4020 KiB | |||
11 | Elfogadva | 1/1 | 4ms | 3976 KiB | |||
12 | Elfogadva | 1/1 | 4ms | 3976 KiB | |||
13 | Elfogadva | 3/3 | 24ms | 6260 KiB | |||
14 | Elfogadva | 3/3 | 24ms | 6276 KiB | |||
15 | Elfogadva | 3/3 | 24ms | 6276 KiB | |||
16 | Elfogadva | 3/3 | 24ms | 6564 KiB | |||
17 | Elfogadva | 3/3 | 24ms | 6608 KiB | |||
18 | Elfogadva | 3/3 | 24ms | 6712 KiB | |||
19 | Elfogadva | 3/3 | 24ms | 6616 KiB | |||
20 | Elfogadva | 3/3 | 24ms | 6900 KiB | |||
21 | Elfogadva | 3/3 | 24ms | 6940 KiB | |||
22 | Elfogadva | 3/3 | 24ms | 6896 KiB |