31612023-02-21 11:35:06TuruTamasHírvivők csoportosítása (40)cpp17Wrong answer 6/4014ms4124 KiB
#include <bits/stdc++.h>
using namespace std;

int N, M, H, K;
vector<bool> been;
vector<pair<int, int>> hirek;

void dfs(int& d, int loc) {
    been[loc] = true;
    for (size_t i = 0; i < hirek.size(); i++)
    {
        if (i == loc || been[i]) continue;
        if (abs(hirek[i].first - hirek[loc].first) + abs(hirek[i].second - hirek[loc].second) <= d) dfs(d, i);
    }
}

void getGroups(int& csoportok, int n) {
    csoportok = 0;
    been.assign(H, false);
    for (size_t i = 0; i < H; i++)
    {
        if (been[i]) continue;
        csoportok++;
        dfs(n, i);
    }
}

int main() {
    cin >> N >> M >> H >> K;
    int x, y;
    for (size_t i = 0; i < H; i++)
    {
        cin >> x >> y;
        hirek.push_back({x, y});
    }
    int csoportok, minn = 0, maxn = N+M, n = log2(N+M);
    int lastn = n;
    while (true) {
        int csoportok;
        getGroups(csoportok, n);
        if (csoportok > K) {
            minn = n;
            n = (n+maxn)/2;
        }
        else if (csoportok < K) {
            maxn = n;
            n = (n+minn)/2;
        }
        else {
            cout << n << "\n";
            return 0;
        }
        if (n == lastn) break;
        lastn = n;
    }
    if (csoportok <= K) {
        cout << n;
    }
    else {
        while (csoportok > K) {
            n++;
            getGroups(csoportok, n);
        }
        cout << n;
    }
}
SubtaskSumTestVerdictTimeMemory
base6/40
1Wrong answer0/03ms2000 KiB
2Accepted0/014ms2364 KiB
3Accepted1/13ms2352 KiB
4Accepted1/13ms2560 KiB
5Wrong answer0/13ms2788 KiB
6Wrong answer0/14ms2880 KiB
7Wrong answer0/13ms2964 KiB
8Wrong answer0/13ms3100 KiB
9Wrong answer0/13ms3316 KiB
10Accepted1/14ms3440 KiB
11Wrong answer0/14ms3512 KiB
12Wrong answer0/14ms3512 KiB
13Accepted3/313ms3540 KiB
14Wrong answer0/39ms3672 KiB
15Wrong answer0/34ms3740 KiB
16Wrong answer0/39ms3728 KiB
17Wrong answer0/34ms3732 KiB
18Wrong answer0/39ms3804 KiB
19Wrong answer0/314ms4124 KiB
20Wrong answer0/314ms4076 KiB
21Wrong answer0/39ms4080 KiB
22Wrong answer0/34ms4008 KiB