#include <bits/stdc++.h>
// #define int long long
#define vi vector<int>
#define ii pair<int, int>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define P 31
#define mod 1'000'000'007
#define inf 1'000'000'000'000
#define pb push_back
#define str string
#define sz(x) (x).size()
#define vvi vector<vi>
#define fun function
#define oopt cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define file freopen("problemname.in", "r", stdin); freopen("pr.out", "w", stdout);
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
using namespace std;
template <class T, int SZ> using arr = array<T, SZ>;
int p[16000005];
int a[4001][4001];
bool ob[16000005];
set<int> pov[16000005];
int par(int x) {return p[x] = (p[x] == x ? x : par(p[x]));};
void zd(int x, int y)
{
x = par(x);
y = par(y);
if (x == y) return;
if (pov[x].size() < pov[y].size())
swap(x, y);
for (int v : pov[y])
pov[x].insert(v);
pov[y].clear();
p[y] = x;
}
int dfs(int u, int p = -1)
{
// cout << u << " <- " << p << "\n";
int rez = 0;
for (int v : pov[u])
if (v != p)
rez = max(rez, dfs(v, u));
return rez+1;
}
vector<ii> pr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
signed main()
{
oopt;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
char c;
cin >> c;
if (c == 'F') a[i][j] = 1;
else if (c == 'R') a[i][j] = 2;
p[i*m+j] = i*m+j;
}
queue<ii> q;
q.push({0, 0});
while (q.size())
{
ii t = q.front();
q.pop();
int i = t.f, j = t.s;
int x = i*m+j, y = 0;
for (ii d : pr)
{
int ni = i+d.f, nj = j+d.s;
y = ni*m+nj;
if (ni < 0 || nj < 0 || ni > n || nj > m || ob[par(y)] || a[ni][nj] == 0) continue;
if (a[ni][nj] != a[i][j]) continue;
zd(x, y);
ob[par(y)] = 1;
q.push({ni, nj});
}
for (ii d : pr)
{
int ni = i+d.f, nj = j+d.s;
y = ni*m+nj;
if (ni < 0 || nj < 0 || ni > n || nj > m || ob[par(y)] || a[ni][nj] == 0) continue;
ob[par(y)] = 1;
// cout << par(x) << " " << par(y) << "t\n";
pov[par(x)].insert(par(y));
pov[par(y)].insert(par(x));
q.push({ni, nj});
}
}
cout << dfs(0) << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
371 ms |
767164 KB |
Output isn't correct |
| 2 |
Correct |
281 ms |
751944 KB |
Output is correct |
| 3 |
Incorrect |
311 ms |
758088 KB |
Output isn't correct |
| 4 |
Incorrect |
349 ms |
757320 KB |
Output isn't correct |
| 5 |
Incorrect |
329 ms |
754624 KB |
Output isn't correct |
| 6 |
Correct |
313 ms |
751944 KB |
Output is correct |
| 7 |
Incorrect |
326 ms |
752128 KB |
Output isn't correct |
| 8 |
Incorrect |
341 ms |
752368 KB |
Output isn't correct |
| 9 |
Incorrect |
346 ms |
752216 KB |
Output isn't correct |
| 10 |
Incorrect |
351 ms |
754584 KB |
Output isn't correct |
| 11 |
Incorrect |
389 ms |
753480 KB |
Output isn't correct |
| 12 |
Incorrect |
411 ms |
757576 KB |
Output isn't correct |
| 13 |
Incorrect |
362 ms |
754692 KB |
Output isn't correct |
| 14 |
Incorrect |
357 ms |
754672 KB |
Output isn't correct |
| 15 |
Incorrect |
398 ms |
764492 KB |
Output isn't correct |
| 16 |
Incorrect |
395 ms |
767260 KB |
Output isn't correct |
| 17 |
Incorrect |
361 ms |
761152 KB |
Output isn't correct |
| 18 |
Incorrect |
360 ms |
757368 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
340 ms |
768568 KB |
Output is correct |
| 2 |
Incorrect |
536 ms |
800076 KB |
Output isn't correct |
| 3 |
Runtime error |
1031 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Incorrect |
582 ms |
822160 KB |
Output isn't correct |
| 5 |
Runtime error |
804 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
1554 ms |
1048576 KB |
Execution killed with signal 9 |
| 7 |
Correct |
309 ms |
768904 KB |
Output is correct |
| 8 |
Correct |
319 ms |
768408 KB |
Output is correct |
| 9 |
Incorrect |
335 ms |
753576 KB |
Output isn't correct |
| 10 |
Correct |
346 ms |
752336 KB |
Output is correct |
| 11 |
Incorrect |
353 ms |
768320 KB |
Output isn't correct |
| 12 |
Correct |
344 ms |
754252 KB |
Output is correct |
| 13 |
Incorrect |
546 ms |
799968 KB |
Output isn't correct |
| 14 |
Incorrect |
459 ms |
780616 KB |
Output isn't correct |
| 15 |
Correct |
445 ms |
785736 KB |
Output is correct |
| 16 |
Incorrect |
489 ms |
775500 KB |
Output isn't correct |
| 17 |
Incorrect |
907 ms |
869984 KB |
Output isn't correct |
| 18 |
Correct |
679 ms |
876644 KB |
Output is correct |
| 19 |
Incorrect |
610 ms |
822080 KB |
Output isn't correct |
| 20 |
Incorrect |
618 ms |
834956 KB |
Output isn't correct |
| 21 |
Incorrect |
965 ms |
960864 KB |
Output isn't correct |
| 22 |
Runtime error |
743 ms |
1048576 KB |
Execution killed with signal 9 |
| 23 |
Incorrect |
1432 ms |
975836 KB |
Output isn't correct |
| 24 |
Correct |
856 ms |
1043460 KB |
Output is correct |
| 25 |
Runtime error |
1275 ms |
1048576 KB |
Execution killed with signal 9 |
| 26 |
Correct |
1203 ms |
866724 KB |
Output is correct |
| 27 |
Runtime error |
1729 ms |
1048576 KB |
Execution killed with signal 9 |
| 28 |
Runtime error |
1664 ms |
1048576 KB |
Execution killed with signal 9 |
| 29 |
Runtime error |
1681 ms |
1048576 KB |
Execution killed with signal 9 |
| 30 |
Execution timed out |
2109 ms |
1048576 KB |
Time limit exceeded |
| 31 |
Runtime error |
1237 ms |
1048576 KB |
Execution killed with signal 9 |
| 32 |
Runtime error |
1624 ms |
1048576 KB |
Execution killed with signal 9 |
