2361 | 2023. 01. 11 12:40:17 | renn | Ciklikus rácsháló gráf | cpp11 | Időlimit túllépés 6/40 | 600ms | 4280 KiB |
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod cin.tie(0); ios::sync_with_stdio(0);
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";
}
void print(vector<vector<int>> s)
{
cout << "-----\n";
for (size_t i = 0; i < N*M; i++)
{
for (size_t j = 0; j < N*M; j++)
{
if(s[i][j] > 300)
cout << "z ";
else
cout << s[i][j] << ' ';
}
cout << "\n\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 / N;
// 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;
}
for(int i = 0; i < N; i++)
{
s[i*M][M-1] = 1;
s[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;
}
// print(s);
arg(s);
size_t a, b;
for (size_t i = 0; i < K; i++)
{
// print(s);
cin >> a >> b;
a--;
b--;
s[a][b] = 1;
s[b][a] = 1;
// cout << maxx << "\n";
arg(s);
cout << maxx << "\n";
}
// print(s);
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 6/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Időlimit túllépés | 0/0 | 600ms | 1732 KiB | |||
3 | Hibás válasz | 0/2 | 2ms | 2296 KiB | |||
4 | Elfogadva | 2/2 | 2ms | 2472 KiB | |||
5 | Hibás válasz | 0/2 | 3ms | 2672 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2896 KiB | |||
7 | Hibás válasz | 0/2 | 20ms | 3396 KiB | |||
8 | Hibás válasz | 0/2 | 20ms | 3204 KiB | |||
9 | Hibás válasz | 0/2 | 20ms | 3484 KiB | |||
10 | Hibás válasz | 0/2 | 7ms | 3380 KiB | |||
11 | Elfogadva | 2/2 | 20ms | 3496 KiB | |||
12 | Hibás válasz | 0/2 | 190ms | 4280 KiB | |||
13 | Hibás válasz | 0/2 | 230ms | 3936 KiB | |||
14 | Hibás válasz | 0/2 | 26ms | 3640 KiB | |||
15 | Hibás válasz | 0/2 | 224ms | 3888 KiB | |||
16 | Hibás válasz | 0/2 | 21ms | 3932 KiB | |||
17 | Hibás válasz | 0/2 | 170ms | 4040 KiB | |||
18 | Hibás válasz | 0/2 | 39ms | 4136 KiB | |||
19 | Hibás válasz | 0/2 | 3ms | 4024 KiB | |||
20 | Hibás válasz | 0/2 | 4ms | 4036 KiB | |||
21 | Hibás válasz | 0/2 | 52ms | 4144 KiB | |||
22 | Időlimit túllépés | 0/2 | 574ms | 3712 KiB |