73012024-01-06 15:22:35anonCiklikus rácsháló gráfcpp17Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/03ms1828 KiB
2Accepted0/0150ms2176 KiB
3Accepted2/23ms2128 KiB
4Accepted2/23ms2340 KiB
5Accepted2/23ms2548 KiB
6Accepted2/23ms2628 KiB
7Accepted2/28ms2868 KiB
8Accepted2/28ms2980 KiB
9Accepted2/28ms3064 KiB
10Accepted2/26ms3188 KiB
11Accepted2/28ms3272 KiB
12Accepted2/237ms3636 KiB
13Accepted2/271ms3956 KiB
14Accepted2/212ms3816 KiB
15Accepted2/268ms3824 KiB
16Accepted2/29ms3940 KiB
17Accepted2/257ms4040 KiB
18Accepted2/223ms4032 KiB
19Accepted2/23ms4028 KiB
20Accepted2/24ms4148 KiB
21Accepted2/227ms4232 KiB
22Accepted2/2152ms4244 KiB