23252023-01-10 14:25:45sztomiCiklikus rácsháló gráfcpp11Hibás válasz 24/4010ms4388 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++){
            for(int k = 0; k < sor; k++){
                for(int l = 0; l < oszlop; l++){
                    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--;
        tav[a][b] = tav[b][a] = 1;

        for(int j = 0; j < sor*oszlop; j++){
            for(int k = 0; 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]] -= 2;
                    if(db[tav[j][k]] == 0){
                        db.erase(tav[j][k]);
                    }
                    tav[j][k] = tav[k][j] = akt;
                    db[akt] += 2;
                }
            }
        }
        cout << db.rbegin()->first << "\n";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base24/40
1Elfogadva0/03ms1828 KiB
2Hibás válasz0/010ms2456 KiB
3Elfogadva2/22ms2352 KiB
4Elfogadva2/22ms2556 KiB
5Elfogadva2/22ms2532 KiB
6Elfogadva2/22ms2728 KiB
7Elfogadva2/23ms2828 KiB
8Elfogadva2/23ms3080 KiB
9Elfogadva2/23ms3136 KiB
10Elfogadva2/22ms3004 KiB
11Hibás válasz0/23ms3284 KiB
12Hibás válasz0/28ms3740 KiB
13Hibás válasz0/27ms3612 KiB
14Elfogadva2/23ms3532 KiB
15Hibás válasz0/26ms3584 KiB
16Elfogadva2/23ms3812 KiB
17Hibás válasz0/24ms3832 KiB
18Hibás válasz0/23ms4032 KiB
19Elfogadva2/22ms3836 KiB
20Hibás válasz0/22ms3848 KiB
21Elfogadva2/23ms4000 KiB
22Hibás válasz0/210ms4388 KiB