16072022-11-28 20:38:47kicsiboglarRácsháló gráfcpp11Elfogadva 50/5065ms4456 KiB
#include <iostream>
#include <vector>
#include <deque>
#define ll long long 

using namespace std;

struct adat
{
    ll f, s, steps;
};
struct element
{
    bool lat;
    vector <ll> sz;
};
ll n, m, i, j, a, b,k,M;

int main()
{
    cin >> n >> m>> M;
    vector <element> x((n*m) + 1);
    for (i = 1; i <= n * m; ++i)
    {
        if (i > m) x[i].sz.push_back(i - m);
        if (i <= (n * m) - m) x[i].sz.push_back(i + m);
        if (i % m != 0) x[i].sz.push_back(i + 1);
        if (i % m != 1) x[i].sz.push_back(i - 1);
    }
    ll maxi = (n - 1) * (m - 1);

    for (k = 1; k <= M; ++k)
    {
        cin >> a >> b;
        x[a].sz.push_back(b);
        x[b].sz.push_back(a);
        maxi = -1;
        for (i = 1; i <= n * m; ++i)
        {
            for (j = 1; j <= n * m; ++j) x[j].lat = false;
            deque <pair<ll, ll> > v;
            v.push_back({ i,0 });
            pair<ll, ll> act;
            x[i].lat = true;
            while (!v.empty())
            {
                act = v[0];
                v.pop_front();
                for (auto e : x[act.first].sz)
                {
                    if (!x[e].lat)
                    {
                        x[e].lat = true;
                        if (act.second + 1 > maxi) maxi = act.second + 1;
                        v.push_back({ e,act.second + 1 });
                    }
                }
            }

        }
        cout<<maxi<<"\n";

    }
}


RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1728 KiB
2Elfogadva0/064ms1868 KiB
3Elfogadva2/22ms2052 KiB
4Elfogadva2/22ms2124 KiB
5Elfogadva2/22ms2256 KiB
6Elfogadva2/23ms2492 KiB
7Elfogadva2/24ms2732 KiB
8Elfogadva2/24ms2824 KiB
9Elfogadva2/24ms2828 KiB
10Elfogadva2/23ms2992 KiB
11Elfogadva2/24ms3232 KiB
12Elfogadva2/213ms3312 KiB
13Elfogadva3/329ms3408 KiB
14Elfogadva3/36ms3608 KiB
15Elfogadva3/330ms3692 KiB
16Elfogadva3/34ms3808 KiB
17Elfogadva3/326ms3928 KiB
18Elfogadva3/310ms4008 KiB
19Elfogadva3/32ms3944 KiB
20Elfogadva3/33ms4188 KiB
21Elfogadva3/313ms4316 KiB
22Elfogadva3/365ms4456 KiB