2326 2023. 01. 10 15:00:38 sztomi Ciklikus rácsháló gráf cpp11 Elfogadva 40/40 7ms 4252 KiB
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9+7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int sor, oszlop, uj;
    cin >> sor >> oszlop >> uj;

    vector<vector<int>> tav(sor*oszlop, vector<int>(sor*oszlop, INF));

    map<int, int> db;
    for(int i = 0; i < sor; i++){
        for(int j = 0; j < oszlop; j++){
            tav[i*oszlop+j][i*oszlop+j] = 0;
            for(int k = 0; k < sor; k++){
                for(int l = 0; l < oszlop; l++){
                    if(i*oszlop+j < k*oszlop+l){
                        tav[k*oszlop+l][i*oszlop+j] = tav[i*oszlop+j][k*oszlop+l] = min(abs(i-k), sor-abs(i-k)) + min(abs(j-l), oszlop-abs(j-l));
                        db[tav[i*oszlop+j][k*oszlop+l]]++;
                    }
                }
            }
        }
    }

    int akt;
    int a, b;
    for(int i = 0; i < uj; i++){
        cin >> a >> b;
        a--;
        b--;
        db[tav[a][b]]--;
        if(db[tav[a][b]] <= 0){
            db.erase(tav[a][b]);
        }
        db[1]++;
        tav[a][b] = tav[b][a] = 1;

        for(int j = 0; j < sor*oszlop; j++){
            for(int k = j+1; k < sor*oszlop; k++){
                akt = min(tav[j][a]+tav[b][k]+1, tav[j][b]+tav[a][k]+1);
                if(akt < tav[j][k]){
                    //cout << j << " " << k << " " << akt << "\n";
                    db[tav[j][k]]--;
                    if(db[tav[j][k]] <= 0){
                        db.erase(tav[j][k]);
                    }
                    tav[j][k] = tav[k][j] = akt;
                    db[akt]++;
                }
            }
        }
        cout << db.rbegin()->first << "\n";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1700 KiB
2 Elfogadva 0/0 7ms 2344 KiB
3 Elfogadva 2/2 2ms 2248 KiB
4 Elfogadva 2/2 2ms 2464 KiB
5 Elfogadva 2/2 2ms 2548 KiB
6 Elfogadva 2/2 2ms 2688 KiB
7 Elfogadva 2/2 3ms 3036 KiB
8 Elfogadva 2/2 3ms 3236 KiB
9 Elfogadva 2/2 3ms 3556 KiB
10 Elfogadva 2/2 2ms 3608 KiB
11 Elfogadva 2/2 2ms 3708 KiB
12 Elfogadva 2/2 6ms 3848 KiB
13 Elfogadva 2/2 4ms 3908 KiB
14 Elfogadva 2/2 3ms 4120 KiB
15 Elfogadva 2/2 4ms 4060 KiB
16 Elfogadva 2/2 2ms 4004 KiB
17 Elfogadva 2/2 4ms 4164 KiB
18 Elfogadva 2/2 3ms 3984 KiB
19 Elfogadva 2/2 2ms 3960 KiB
20 Elfogadva 2/2 2ms 3972 KiB
21 Elfogadva 2/2 3ms 3992 KiB
22 Elfogadva 2/2 7ms 4252 KiB