3503 2023. 02. 28 13:44:40 Ablablabla Rácsháló gráf cpp17 Elfogadva 50/50 10ms 4324 KiB 
#include <bits/stdc++.h>


using namespace std;


int main()
{
    int n, m, ujaksz;
    cin >> n >> m >> ujaksz;
    int szam = n * m;
    vector<vector<int>> tavok(szam, vector<int>(szam, 100000));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                for(int l = 0; l < n; l++){
                    tavok[j * m + i][l * m + k] = abs(i - k) + abs(j - l);
                }
            }
        }
    }

    /*for(int i = 0; i < szam; i++){
        for(int j = 0; j < szam; j++){
            cout << tavok[i][j] << " ";
        }
        cout << "\n";
    }*/
    vector<int> valasz(ujaksz, 0);
    for(int k = 0; k < ujaksz; k++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        tavok[a][b] = 1;
        tavok[b][a] = 1;
        for(int i = 0; i < szam; i++){
            for(int j = 0; j < szam; j++){
                if(tavok[i][j] > tavok[i][a] + tavok[j][a]){
                    tavok[i][j] = tavok[i][a] + tavok[j][a];
                }
            }
        }

        for(int i = 0; i < szam; i++){
            for(int j = 0; j < szam; j++){
                if(tavok[i][j] > tavok[i][b] + tavok[j][b]){
                    tavok[i][j] = tavok[i][b] + tavok[j][b];
                }
            }
        }

        int maxi = 0;
        for(int i = 0; i < szam; i++){
            for(int j = i; j < szam; j++){
                if(tavok[i][j] > maxi){
                    maxi = tavok[i][j];
                }
            }
        }

        valasz[k] = maxi;
    }

    for(int i = 0; i < ujaksz; i++){
        cout << valasz[i] << "\n";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1812 KiB
2 Elfogadva 0/0 10ms 2424 KiB
3 Elfogadva 2/2 3ms 2216 KiB
4 Elfogadva 2/2 3ms 2432 KiB
5 Elfogadva 2/2 3ms 2644 KiB
6 Elfogadva 2/2 3ms 2860 KiB
7 Elfogadva 2/2 3ms 2980 KiB
8 Elfogadva 2/2 3ms 3048 KiB
9 Elfogadva 2/2 3ms 3056 KiB
10 Elfogadva 2/2 3ms 3056 KiB
11 Elfogadva 2/2 3ms 3404 KiB
12 Elfogadva 2/2 4ms 3796 KiB
13 Elfogadva 3/3 6ms 3672 KiB
14 Elfogadva 3/3 3ms 3788 KiB
15 Elfogadva 3/3 6ms 3788 KiB
16 Elfogadva 3/3 3ms 3968 KiB
17 Elfogadva 3/3 6ms 4076 KiB
18 Elfogadva 3/3 4ms 3944 KiB
19 Elfogadva 3/3 3ms 4172 KiB
20 Elfogadva 3/3 3ms 4044 KiB
21 Elfogadva 3/3 4ms 4060 KiB
22 Elfogadva 3/3 9ms 4324 KiB