#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int N = 3003;
char c[N][N];
int used[N][N];
vector<set<int>> g;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> c[i][j];
}
}
int tmp = 0, num = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m - 2; ++j) {
if (c[i][j] == 'R' && c[i][j + 1] == 'G' && c[i][j + 2] == 'W') {
tmp++; num++;
used[i][j] = used[i][j + 1] = used[i][j + 2] = num;
}
}
}
int original = num;
g.resize(original + 1);
vector<bool> in_que(num + 1);
for (int i = 0; i < n - 2; ++i) {
for (int j = 0; j < m; ++j) {
if (c[i][j] == 'R' && c[i + 1][j] == 'G' && c[i + 2][j] == 'W') {
num++;
g.push_back({});
for (int k = 0; k < 3; ++k) {
if (used[i + k][j]) {
g[num].insert(used[i + k][j]);
g[used[i + k][j]].insert(num);
}
}
if (g[num].size() == 0) {
tmp++;
}
}
}
}
int ans = tmp;
queue<int> que;
for (int i = 1; i <= original; ++i) {
for (int u : g[i]) {
if (g[u].size() == 1) {
in_que[i] = true;
que.push(i);
break;
}
}
}
while (!que.empty()) {
int v = que.front();
que.pop();
ans--;
for (int u : g[v]) {
g[u].erase(v);
if (g[u].size() == 0) {
ans++;
} else if (g[u].size() == 1) {
assert(!g[u].empty());
int z = *g[u].begin();
if (!in_que[z]) {
que.push(*g[u].begin());
assert(z <= original);
in_que[z] = true;
}
}
}
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
0 ms |
2392 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2392 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
0 ms |
2396 KB |
Output is correct |
15 |
Correct |
0 ms |
2396 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
0 ms |
2392 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2392 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
0 ms |
2396 KB |
Output is correct |
15 |
Correct |
0 ms |
2396 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
1 ms |
2396 KB |
Output is correct |
19 |
Correct |
0 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
2392 KB |
Output is correct |
21 |
Correct |
0 ms |
2396 KB |
Output is correct |
22 |
Correct |
0 ms |
2396 KB |
Output is correct |
23 |
Correct |
1 ms |
2392 KB |
Output is correct |
24 |
Correct |
1 ms |
2396 KB |
Output is correct |
25 |
Correct |
0 ms |
2396 KB |
Output is correct |
26 |
Correct |
1 ms |
2396 KB |
Output is correct |
27 |
Correct |
1 ms |
2396 KB |
Output is correct |
28 |
Correct |
1 ms |
2392 KB |
Output is correct |
29 |
Correct |
1 ms |
2396 KB |
Output is correct |
30 |
Correct |
1 ms |
2396 KB |
Output is correct |
31 |
Correct |
1 ms |
2396 KB |
Output is correct |
32 |
Correct |
0 ms |
2396 KB |
Output is correct |
33 |
Correct |
1 ms |
2392 KB |
Output is correct |
34 |
Correct |
1 ms |
2396 KB |
Output is correct |
35 |
Correct |
0 ms |
2396 KB |
Output is correct |
36 |
Correct |
1 ms |
2396 KB |
Output is correct |
37 |
Correct |
1 ms |
2648 KB |
Output is correct |
38 |
Correct |
1 ms |
2396 KB |
Output is correct |
39 |
Correct |
1 ms |
2396 KB |
Output is correct |
40 |
Correct |
1 ms |
2396 KB |
Output is correct |
41 |
Correct |
1 ms |
2396 KB |
Output is correct |
42 |
Correct |
1 ms |
2396 KB |
Output is correct |
43 |
Correct |
1 ms |
2396 KB |
Output is correct |
44 |
Correct |
1 ms |
2396 KB |
Output is correct |
45 |
Correct |
1 ms |
2396 KB |
Output is correct |
46 |
Correct |
0 ms |
2396 KB |
Output is correct |
47 |
Correct |
0 ms |
2396 KB |
Output is correct |
48 |
Correct |
1 ms |
2396 KB |
Output is correct |
49 |
Correct |
1 ms |
2396 KB |
Output is correct |
50 |
Correct |
0 ms |
2396 KB |
Output is correct |
51 |
Correct |
0 ms |
2396 KB |
Output is correct |
52 |
Correct |
1 ms |
2396 KB |
Output is correct |
53 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
0 ms |
2392 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2392 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
0 ms |
2396 KB |
Output is correct |
15 |
Correct |
0 ms |
2396 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
1 ms |
2396 KB |
Output is correct |
19 |
Correct |
0 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
2392 KB |
Output is correct |
21 |
Correct |
0 ms |
2396 KB |
Output is correct |
22 |
Correct |
0 ms |
2396 KB |
Output is correct |
23 |
Correct |
1 ms |
2392 KB |
Output is correct |
24 |
Correct |
1 ms |
2396 KB |
Output is correct |
25 |
Correct |
0 ms |
2396 KB |
Output is correct |
26 |
Correct |
1 ms |
2396 KB |
Output is correct |
27 |
Correct |
1 ms |
2396 KB |
Output is correct |
28 |
Correct |
1 ms |
2392 KB |
Output is correct |
29 |
Correct |
1 ms |
2396 KB |
Output is correct |
30 |
Correct |
1 ms |
2396 KB |
Output is correct |
31 |
Correct |
1 ms |
2396 KB |
Output is correct |
32 |
Correct |
0 ms |
2396 KB |
Output is correct |
33 |
Correct |
1 ms |
2392 KB |
Output is correct |
34 |
Correct |
1 ms |
2396 KB |
Output is correct |
35 |
Correct |
0 ms |
2396 KB |
Output is correct |
36 |
Correct |
1 ms |
2396 KB |
Output is correct |
37 |
Correct |
1 ms |
2648 KB |
Output is correct |
38 |
Correct |
1 ms |
2396 KB |
Output is correct |
39 |
Correct |
1 ms |
2396 KB |
Output is correct |
40 |
Correct |
1 ms |
2396 KB |
Output is correct |
41 |
Correct |
1 ms |
2396 KB |
Output is correct |
42 |
Correct |
1 ms |
2396 KB |
Output is correct |
43 |
Correct |
1 ms |
2396 KB |
Output is correct |
44 |
Correct |
1 ms |
2396 KB |
Output is correct |
45 |
Correct |
1 ms |
2396 KB |
Output is correct |
46 |
Correct |
0 ms |
2396 KB |
Output is correct |
47 |
Correct |
0 ms |
2396 KB |
Output is correct |
48 |
Correct |
1 ms |
2396 KB |
Output is correct |
49 |
Correct |
1 ms |
2396 KB |
Output is correct |
50 |
Correct |
0 ms |
2396 KB |
Output is correct |
51 |
Correct |
0 ms |
2396 KB |
Output is correct |
52 |
Correct |
1 ms |
2396 KB |
Output is correct |
53 |
Correct |
1 ms |
2396 KB |
Output is correct |
54 |
Correct |
1 ms |
2396 KB |
Output is correct |
55 |
Correct |
2 ms |
9564 KB |
Output is correct |
56 |
Correct |
1 ms |
2652 KB |
Output is correct |
57 |
Correct |
6 ms |
31580 KB |
Output is correct |
58 |
Correct |
26 ms |
27096 KB |
Output is correct |
59 |
Correct |
221 ms |
87376 KB |
Output is correct |
60 |
Correct |
215 ms |
87168 KB |
Output is correct |
61 |
Correct |
222 ms |
118984 KB |
Output is correct |
62 |
Correct |
1 ms |
2396 KB |
Output is correct |
63 |
Correct |
219 ms |
116268 KB |
Output is correct |
64 |
Runtime error |
157 ms |
262144 KB |
Execution killed with signal 9 |
65 |
Halted |
0 ms |
0 KB |
- |