31652023-02-21 12:01:43rennHírvivők csoportosítása (40)cpp17Időlimit túllépés 4/40476ms8352 KiB
#include <bits/stdc++.h>
using namespace std;

#define GOTTAGOFAST cin.tie(0); ios::sync_with_stdio(0);

int cnt;

inline bool megold(vector<vector<int>> &graf, int cl, int &k, vector<bool> &volt)
{
    fill(volt.begin(), volt.end(), false);
    
    cnt = 0;
    queue<int> next;

    for(int i = 0; i < graf.size(); ++i)
    {
        if(volt[i]) continue;

        cnt++;

        next.push(i);
        while(!next.empty())
        {
            volt.at(next.front()) = true;
            for(int j = 0; j < graf.size(); ++j)
            {
                if(volt[j] || graf.at(next.front()).at(j) == -1) continue;

                if(graf.at(next.front()).at(j) < cl)
                {
                    next.push(j);
                }
            }
            next.pop();
        }
    }

    return cnt <= k;
}

int main()
{

    GOTTAGOFAST

    int x, y, n, k;
    cin >> x >> y >> n >> k;

    vector<vector<int>> graf(n, vector<int>(n, -1));
    vector<pair<int, int>> pontok(n);
    vector<bool> volt(n);
    int a, b;
    for (size_t i = 0; i < n; i++)
    {
        cin >> a >> b;
        pontok.at(i) = {a, b};
    }

    int left = INT_MAX, right = -1, mid;

    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            if(i == j || graf.at(i).at(j) != -1) continue;
            graf.at(i).at(j) = abs(pontok.at(i).first-pontok.at(j).first)+abs(pontok.at(i).second-pontok.at(j).second);
            left = min(graf.at(i).at(j), left);
            right = max(graf.at(i).at(j), right);
        }
        
    }
    
    while(left < right)
    {
        mid = left+(right-left)/2;

        if(megold(graf, mid, k, volt))
        {
            right = mid-1;
        }
        else
        {
            left = mid+1;
        }
    }

    cout << right << "\n";

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base4/40
1Elfogadva0/03ms1832 KiB
2Időlimit túllépés0/0467ms4180 KiB
3Hibás válasz0/112ms2476 KiB
4Elfogadva1/13ms2336 KiB
5Elfogadva1/1282ms3116 KiB
6Időlimit túllépés0/1458ms6316 KiB
7Időlimit túllépés0/1451ms3960 KiB
8Elfogadva1/129ms3212 KiB
9Hibás válasz0/117ms3232 KiB
10Elfogadva1/1111ms3968 KiB
11Hibás válasz0/1238ms4104 KiB
12Időlimit túllépés0/1470ms8352 KiB
13Időlimit túllépés0/3463ms4636 KiB
14Időlimit túllépés0/3476ms4300 KiB
15Időlimit túllépés0/3467ms5320 KiB
16Időlimit túllépés0/3451ms5284 KiB
17Időlimit túllépés0/3451ms5480 KiB
18Időlimit túllépés0/3439ms6580 KiB
19Időlimit túllépés0/3463ms5044 KiB
20Időlimit túllépés0/3467ms5344 KiB
21Időlimit túllépés0/3456ms4872 KiB
22Időlimit túllépés0/3453ms4912 KiB