#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 a[4001][4001];
int comp[4001][4001];
vi graf[20000001];
set<ii> pov;
vector<ii> pr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void dfs(int i, int j, int nc, int n, int m)
{
if (comp[i][j]) return;
comp[i][j] = nc;
for (ii d : pr)
{
int ni = i+d.f, nj = j+d.s;
if (ni < 0 || nj < 0 || nj >= m || ni >= n || a[ni][nj] != a[i][j]) continue;
dfs(ni, nj, nc, n, m);
}
}
int dfs1(int u, int p = -1)
{
// cout << u << " " << p << "\n";
int rez = 0;
for (int v : graf[u])
if (v != p)
rez = max(rez, dfs1(v, u));
return rez+1;
}
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;
}
int nc = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (a[i][j])
dfs(i, j, nc++, n, m);
// for (int i = 0; i < n; i++)
// for (int j = 0; j < m; j++)
// cout << comp[i][j] << " \n"[j == m-1];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (a[i][j] == 0) continue;
for (ii d : pr)
{
int ni = i+d.f, nj = j+d.s;
if (ni < 0 || nj < 0 || nj >= m || ni >= n || comp[ni][nj] == comp[i][j] || !a[ni][nj])
continue;
if (pov.find({comp[ni][nj], comp[i][j]}) != pov.end()) continue;
// cout << a[i][j] << " " << a[ni][nj] << " " << comp[i][j] << " " << comp[ni][nj] << "\n";
pov.insert({comp[ni][nj], comp[i][j]});
pov.insert({comp[i][j], comp[ni][nj]});
graf[comp[ni][nj]].pb(comp[i][j]);
graf[comp[i][j]].pb(comp[ni][nj]);
}
}
cout << dfs1(comp[0][0]) << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
671 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Correct |
111 ms |
470184 KB |
Output is correct |
| 3 |
Runtime error |
640 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
694 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
654 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Correct |
108 ms |
470296 KB |
Output is correct |
| 7 |
Runtime error |
641 ms |
1048576 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
635 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
629 ms |
1048576 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
630 ms |
1048576 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
1116 ms |
1048576 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
678 ms |
1048576 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
636 ms |
1048576 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
653 ms |
1048576 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
684 ms |
1048576 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
648 ms |
1048576 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
641 ms |
1048576 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
708 ms |
1048576 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
501900 KB |
Output is correct |
| 2 |
Runtime error |
798 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
1638 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
861 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Execution timed out |
2118 ms |
988960 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2093 ms |
769724 KB |
Time limit exceeded |
| 7 |
Correct |
173 ms |
503368 KB |
Output is correct |
| 8 |
Correct |
191 ms |
501936 KB |
Output is correct |
| 9 |
Runtime error |
974 ms |
1048576 KB |
Execution killed with signal 9 |
| 10 |
Correct |
148 ms |
470856 KB |
Output is correct |
| 11 |
Execution timed out |
2089 ms |
532704 KB |
Time limit exceeded |
| 12 |
Correct |
134 ms |
473160 KB |
Output is correct |
| 13 |
Runtime error |
824 ms |
1048576 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
1861 ms |
1048576 KB |
Execution killed with signal 9 |
| 15 |
Correct |
283 ms |
511560 KB |
Output is correct |
| 16 |
Runtime error |
724 ms |
1048576 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
1039 ms |
1048576 KB |
Execution killed with signal 9 |
| 18 |
Correct |
825 ms |
614632 KB |
Output is correct |
| 19 |
Runtime error |
841 ms |
1048576 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
933 ms |
1048576 KB |
Execution killed with signal 9 |
| 21 |
Execution timed out |
2084 ms |
697236 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2101 ms |
986120 KB |
Time limit exceeded |
| 23 |
Runtime error |
1505 ms |
1048576 KB |
Execution killed with signal 9 |
| 24 |
Correct |
1308 ms |
793464 KB |
Output is correct |
| 25 |
Execution timed out |
2088 ms |
842892 KB |
Time limit exceeded |
| 26 |
Runtime error |
738 ms |
1048576 KB |
Execution killed with signal 9 |
| 27 |
Correct |
990 ms |
833352 KB |
Output is correct |
| 28 |
Execution timed out |
2083 ms |
895836 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2050 ms |
1048576 KB |
Time limit exceeded |
| 30 |
Runtime error |
1783 ms |
1048576 KB |
Execution killed with signal 9 |
| 31 |
Execution timed out |
2082 ms |
711448 KB |
Time limit exceeded |
| 32 |
Runtime error |
1326 ms |
1048576 KB |
Execution killed with signal 9 |
