73012024-01-06 15:22:35anonCiklikus rácsháló gráfcpp17Elfogadva 40/40152ms4244 KiB
#include <bits/stdc++.h>
#define MOD(a, b) ((((a) % (b)) + (b)) % (b))
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
const ll D4[][2] = {{ -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 }};
int main() {
    FastIO;
    ll i, j, k, u, v, ans, N, M, K;
    cin >> N >> M >> K;
    vector<vector<ll>> graph(N * M + 1);
    for(i = 0; i < N; i++) {
        for(j = 0; j < M; j++) {
            for(k = 0; k < 4; k++)
                graph[i * M + j + 1].push_back(MOD(i + D4[k][1], N) * M + MOD(j + D4[k][0], M) + 1);
        }
    }
    while(K--) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        ans = -1;
        for(i = 1; i <= N * M; i++) {
            vector<bool> vis(N * M + 1, false);
            queue<array<ll, 2>> q;
            q.push({ i, 0 });
            while(!q.empty()) {
                auto [cv, d] = q.front();
                q.pop();
                if(vis[cv])
                    continue;
                vis[cv] = true;
                ans = max(ans, d);
                for(const auto &x : graph[cv])
                    q.push({ x, d + 1});
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/03ms1828 KiB
2Elfogadva0/0150ms2176 KiB
3Elfogadva2/23ms2128 KiB
4Elfogadva2/23ms2340 KiB
5Elfogadva2/23ms2548 KiB
6Elfogadva2/23ms2628 KiB
7Elfogadva2/28ms2868 KiB
8Elfogadva2/28ms2980 KiB
9Elfogadva2/28ms3064 KiB
10Elfogadva2/26ms3188 KiB
11Elfogadva2/28ms3272 KiB
12Elfogadva2/237ms3636 KiB
13Elfogadva2/271ms3956 KiB
14Elfogadva2/212ms3816 KiB
15Elfogadva2/268ms3824 KiB
16Elfogadva2/29ms3940 KiB
17Elfogadva2/257ms4040 KiB
18Elfogadva2/223ms4032 KiB
19Elfogadva2/23ms4028 KiB
20Elfogadva2/24ms4148 KiB
21Elfogadva2/227ms4232 KiB
22Elfogadva2/2152ms4244 KiB