23652023-01-11 13:55:41rennCiklikus rácsháló gráfcpp11Time limit exceeded 36/40600ms4520 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)
        for(int i = 0; i < N; i++)
        {
            s[i*M][i*M+M-1] = 1;
            s[i*M+M-1][i*M] = 1;
        }

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

    arg(s);

    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
base36/40
1Accepted0/03ms1828 KiB
2Time limit exceeded0/0600ms1692 KiB
3Wrong answer0/22ms2276 KiB
4Accepted2/22ms2456 KiB
5Accepted2/23ms2652 KiB
6Accepted2/23ms2836 KiB
7Accepted2/220ms3256 KiB
8Accepted2/220ms3608 KiB
9Accepted2/220ms3412 KiB
10Accepted2/27ms3632 KiB
11Accepted2/220ms3736 KiB
12Accepted2/2192ms4520 KiB
13Accepted2/2231ms4160 KiB
14Accepted2/226ms3948 KiB
15Accepted2/2225ms4112 KiB
16Accepted2/221ms4188 KiB
17Accepted2/2171ms4288 KiB
18Accepted2/239ms4064 KiB
19Accepted2/23ms4012 KiB
20Accepted2/24ms4024 KiB
21Accepted2/252ms4068 KiB
22Time limit exceeded0/2568ms3652 KiB