72922024-01-06 12:40:36anonCiklikus rácsháló gráfcpp17Időlimit túllépés 38/40521ms4112 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 INF = (1LL << 62);
const ll D4[][2] = {{ -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 }};
int main() {
    FastIO;
    ll i, j, u, v, nx, ny, ans, N, M, K;
    cin >> N >> M >> K;
    vector<vector<ll>> graph(N * M + 1);
    while(K--) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        ans = -INF;
        for(i = 1; i <= N * M * 2 / 3 + 1; 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(j = 0; j < 4; j++) {
                    nx = MOD((cv - 1) % M + D4[j][0], M);
                    ny = MOD((cv - 1) / M + D4[j][1], N);
                    u = ny * M + nx + 1;
                    if(!vis[u])
                        q.push({ u, d + 1 });
                }
                for(const auto &x : graph[cv]) {
                    if(!vis[x])
                        q.push({ x, d + 1});
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base38/40
1Elfogadva0/03ms1824 KiB
2Időlimit túllépés0/0519ms2068 KiB
3Elfogadva2/23ms2104 KiB
4Elfogadva2/24ms2232 KiB
5Elfogadva2/24ms2464 KiB
6Elfogadva2/26ms2672 KiB
7Elfogadva2/227ms2872 KiB
8Elfogadva2/228ms3088 KiB
9Elfogadva2/227ms3304 KiB
10Elfogadva2/214ms3376 KiB
11Elfogadva2/227ms3508 KiB
12Elfogadva2/2134ms3648 KiB
13Elfogadva2/2233ms3736 KiB
14Elfogadva2/235ms3820 KiB
15Elfogadva2/2237ms3864 KiB
16Elfogadva2/228ms3872 KiB
17Elfogadva2/2194ms3876 KiB
18Elfogadva2/271ms4112 KiB
19Elfogadva2/24ms3988 KiB
20Elfogadva2/28ms3904 KiB
21Elfogadva2/286ms3904 KiB
22Időlimit túllépés0/2521ms3912 KiB