#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 (par(v) != p)
rez = max(rez, dfs(par(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(par(0)) << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
355 ms |
767304 KB |
Output isn't correct |
| 2 |
Correct |
271 ms |
751996 KB |
Output is correct |
| 3 |
Incorrect |
265 ms |
752168 KB |
Output isn't correct |
| 4 |
Incorrect |
299 ms |
757240 KB |
Output isn't correct |
| 5 |
Incorrect |
288 ms |
754760 KB |
Output isn't correct |
| 6 |
Correct |
273 ms |
751944 KB |
Output is correct |
| 7 |
Incorrect |
282 ms |
752200 KB |
Output isn't correct |
| 8 |
Incorrect |
293 ms |
752304 KB |
Output isn't correct |
| 9 |
Incorrect |
309 ms |
752456 KB |
Output isn't correct |
| 10 |
Incorrect |
298 ms |
754504 KB |
Output isn't correct |
| 11 |
Incorrect |
308 ms |
753480 KB |
Output isn't correct |
| 12 |
Incorrect |
301 ms |
757804 KB |
Output isn't correct |
| 13 |
Incorrect |
307 ms |
754764 KB |
Output isn't correct |
| 14 |
Incorrect |
318 ms |
754616 KB |
Output isn't correct |
| 15 |
Incorrect |
360 ms |
764416 KB |
Output isn't correct |
| 16 |
Incorrect |
366 ms |
767280 KB |
Output isn't correct |
| 17 |
Incorrect |
344 ms |
761028 KB |
Output isn't correct |
| 18 |
Incorrect |
335 ms |
757320 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
768328 KB |
Output is correct |
| 2 |
Incorrect |
544 ms |
800120 KB |
Output isn't correct |
| 3 |
Runtime error |
1022 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Incorrect |
586 ms |
820552 KB |
Output isn't correct |
| 5 |
Runtime error |
712 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
1646 ms |
1048576 KB |
Execution killed with signal 9 |
| 7 |
Correct |
314 ms |
768836 KB |
Output is correct |
| 8 |
Correct |
309 ms |
768404 KB |
Output is correct |
| 9 |
Incorrect |
312 ms |
753612 KB |
Output isn't correct |
| 10 |
Correct |
297 ms |
752536 KB |
Output is correct |
| 11 |
Incorrect |
302 ms |
768328 KB |
Output isn't correct |
| 12 |
Correct |
296 ms |
754428 KB |
Output is correct |
| 13 |
Incorrect |
518 ms |
800692 KB |
Output isn't correct |
| 14 |
Incorrect |
449 ms |
780620 KB |
Output isn't correct |
| 15 |
Correct |
393 ms |
787548 KB |
Output is correct |
| 16 |
Incorrect |
413 ms |
775340 KB |
Output isn't correct |
| 17 |
Incorrect |
844 ms |
868424 KB |
Output isn't correct |
| 18 |
Correct |
694 ms |
883528 KB |
Output is correct |
| 19 |
Incorrect |
626 ms |
822336 KB |
Output isn't correct |
| 20 |
Incorrect |
575 ms |
836424 KB |
Output isn't correct |
| 21 |
Incorrect |
943 ms |
966912 KB |
Output isn't correct |
| 22 |
Runtime error |
724 ms |
1048576 KB |
Execution killed with signal 9 |
| 23 |
Incorrect |
1442 ms |
972328 KB |
Output isn't correct |
| 24 |
Runtime error |
830 ms |
1048576 KB |
Execution killed with signal 9 |
| 25 |
Runtime error |
1232 ms |
1048576 KB |
Execution killed with signal 9 |
| 26 |
Correct |
1170 ms |
854724 KB |
Output is correct |
| 27 |
Runtime error |
1731 ms |
1048580 KB |
Execution killed with signal 9 |
| 28 |
Runtime error |
1679 ms |
1048576 KB |
Execution killed with signal 9 |
| 29 |
Runtime error |
1805 ms |
1048576 KB |
Execution killed with signal 9 |
| 30 |
Execution timed out |
2079 ms |
1048576 KB |
Time limit exceeded |
| 31 |
Runtime error |
1200 ms |
1048576 KB |
Execution killed with signal 9 |
| 32 |
Runtime error |
1630 ms |
1048576 KB |
Execution killed with signal 9 |
