23672023-01-11 14:20:00rennCiklikus rácsháló gráfcpp11Time limit exceeded 38/40600ms4324 KiB
#include <bits/stdc++.h>
using namespace std;


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

void print(vector<vector<int>> &s);


int N, M, K, maxx = INT_MAX, L = 500;

void arg(vector<vector<int>> s) {
    for (size_t k = 0; k < N*M; k++)
    {
        for (size_t i = 0; i < N*M; i++)
        {
            for (size_t j = 0; j < N*M; j++)
            {
                s[i][j] = min(s[i][k] + s[k][j], s[i][j]);
            } // j
        } // i
    } // k

    int temp = -1, t;
    for(auto &i : s)
    {
        t = *max_element(i.begin(), i.end());
        temp = t > temp ? t : temp;
    }
    maxx = temp;
    // cout << "KESZ AZ ARGS\n";
    // print(s);

}

void print(vector<vector<int>> s)
{
    cout << "-----\n";
    for (size_t i = 0; i < N*M; i++)
    {
        cout << i+1 << ": \n";
        for (size_t k = 0; k < N; k++)
        {
            for (size_t j = 0, g; j < M; j++)
            {
                g = s[i][k*(M-1)+j];
                cout << setw(3) << (g > 200 ? "z" : std::to_string(g)) << " ";
            }
            cout << "\n";
            
        }
        cout << "\n";
        
    }
    
    cout << "-----\n";
}

int main() {

    InTheNameOfGod

    cin >> N >> M >> K;
    vector<vector<int>> s(N*M, vector<int>(N*M, L));

    // cout << "d0\n";

    for (size_t i = 0; i < N*M; i++)
    {
        int sor = i / M;
        int osz = i % M;
        // cout << i << " -> " << sor << ":" << osz << "\n";
        if (sor != 0) {
            // cout << "d1\n";
            s[i - M][i] = 1;
            s[i][i - M] = 1;
            // cout << "d2\n";
        }
        if (osz != 0) {
            // cout << "d3\n";
            s[i][i - 1] = 1;
            s[i - 1][i] = 1;
            // cout << "d4\n";
        }
        if (sor != N - 1) {
            // cout << "d5\n";
            s[i][i + M] = 1;
            s[i + M][i] = 1;
            // cout << "d6\n";
        }
        if (osz != M - 1) {
            // cout << "d7\n";
            s[i + 1][i] = 1;
            s[i][i + 1] = 1;
            // cout << "d8\n";
        }
        // cout << "d9\n";
        s[i][i] = 0;
    }

    if(N > 1 && M > 1)
    {
        for(int i = 0; i < N; i++)
        {
            s[i*M][i*M+M-1] = 1;
            s[i*M+M-1][i*M] = 1;
        }
        for(int i = 0; i < M; i++)
        {
            s[i][M*(N-1)+i] = 1;
            s[M*(N-1)+i][i] = 1;
        }
    }
    else if(N > 1)
    {
        s[0][N-1] = 1;
        s[N-1][0] = 1;
    }
    else if(M > 1)
    {
        s[0][M-1] = 1;
        s[M-1][0] = 1;
    }

    size_t a, b;
    for (size_t i = 0; i <K; i++)
    {
        cin >> a >> b;
        a--;
        b--;
        s[a][b] = 1;
        s[b][a] = 1;
        arg(s);
        cout << maxx << "\n";
    }
    // print(s);
    
}
SubtaskSumTestVerdictTimeMemory
base38/40
1Accepted0/03ms1824 KiB
2Time limit exceeded0/0600ms1788 KiB
3Accepted2/22ms2088 KiB
4Accepted2/22ms2260 KiB
5Accepted2/23ms2484 KiB
6Accepted2/23ms2560 KiB
7Accepted2/218ms2996 KiB
8Accepted2/218ms3180 KiB
9Accepted2/218ms3188 KiB
10Accepted2/27ms3300 KiB
11Accepted2/218ms3556 KiB
12Accepted2/2179ms4324 KiB
13Accepted2/2225ms4020 KiB
14Accepted2/224ms3588 KiB
15Accepted2/2221ms3836 KiB
16Accepted2/219ms3852 KiB
17Accepted2/2166ms4120 KiB
18Accepted2/237ms3956 KiB
19Accepted2/23ms3976 KiB
20Accepted2/24ms4208 KiB
21Accepted2/250ms4312 KiB
22Time limit exceeded0/2574ms3860 KiB