3263 | 2023. 02. 23 14:58:26 | sztomi | Hírvivők csoportosítása (40) | cpp11 | Elfogadva 40/40 | 25ms | 8304 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int tav(pii a, pii b){
return abs(a.first - b.first) + abs(a.second - b.second);
}
int h;
vector<vector<pii>> graf;
vector<int> volt;
int ido = 0;
void dfs(int akt, int& l){
volt[akt] = ido;
for(auto kov : graf[akt]){
if(kov.first > l) break;
if(volt[kov.second] >= ido) continue;
dfs(kov.second, l);
}
}
int csoport_db(int l){
int ki = 0;
ido++;
for(int i = 0; i < h; i++){
if(volt[i] < ido){
ki++;
dfs(i, l);
}
}
return ki;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k;
cin >> n >> m >> h >> k;
// tav, kovi
graf.assign(h, vector<pii>());
volt.assign(h, 0);
vector<pii> hely(h);
for(int i = 0; i < h; i++){
cin >> hely[i].first >> hely[i].second;
}
int t;
for(int i = 0; i < h; i++){
for(int j = i+1; j < h; j++){
t = tav(hely[i], hely[j]);
graf[i].push_back({t, j});
graf[j].push_back({t, i});
}
}
for(int i = 0; i < h; i++){
sort(graf[i].begin(), graf[i].end());
}
int ki = -1;
int l = 0, r = 20200;
int mid;
while(l <= r){
mid = (l+r) / 2;
if(csoport_db(mid) <= k){
r = mid - 1;
ki = mid;
}
else{
l = mid + 1;
}
}
cout << ki << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 40/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 19ms | 5604 KiB | |||
3 | Elfogadva | 1/1 | 4ms | 2484 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2612 KiB | |||
5 | Elfogadva | 1/1 | 6ms | 3272 KiB | |||
6 | Elfogadva | 1/1 | 6ms | 3524 KiB | |||
7 | Elfogadva | 1/1 | 4ms | 3084 KiB | |||
8 | Elfogadva | 1/1 | 4ms | 3300 KiB | |||
9 | Elfogadva | 1/1 | 3ms | 3380 KiB | |||
10 | Elfogadva | 1/1 | 6ms | 3876 KiB | |||
11 | Elfogadva | 1/1 | 6ms | 4128 KiB | |||
12 | Elfogadva | 1/1 | 6ms | 4092 KiB | |||
13 | Elfogadva | 3/3 | 24ms | 7404 KiB | |||
14 | Elfogadva | 3/3 | 25ms | 7344 KiB | |||
15 | Elfogadva | 3/3 | 25ms | 7488 KiB | |||
16 | Elfogadva | 3/3 | 25ms | 7600 KiB | |||
17 | Elfogadva | 3/3 | 24ms | 7812 KiB | |||
18 | Elfogadva | 3/3 | 24ms | 8024 KiB | |||
19 | Elfogadva | 3/3 | 24ms | 8112 KiB | |||
20 | Elfogadva | 3/3 | 24ms | 8304 KiB | |||
21 | Elfogadva | 3/3 | 24ms | 8256 KiB | |||
22 | Elfogadva | 3/3 | 25ms | 8304 KiB |