#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define entr cerr << endl;
#define spac cerr << ' ';
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) x.begin(), x.end()
#define unilize(x) x.resize(unique(BAE(x)) - x.begin())
#define unisort(x) sort(BAE(x)); unilize(x);
using namespace std;
typedef long long ll;
const int mxn = 3010;
char c[mxn][mxn];
vector<pii> EV;
const int mxN = (int)(9e6) + 3000;
bool vis[mxN], can[mxN];
vector<int> E[mxN];
int p[mxn][mxn];
void dfs(int v, int& sz, bool now, int &black){
sz++;
vis[v] = true;
if(now) black++;
for(auto &u:E[v]){
if(!vis[u]){
dfs(u, sz, !now, black);
}
}
}
void check(int x, int y, int ind){
if(p[x][y] == 0){
p[x][y] = ind;
}
else{
EV.pb({p[x][y], ind});
}
}
int main(){
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false); cin.tie(0);
int n, m;
cin >> n >> m;
loop(i,0,n){
loop(j,0,m){
cin >> c[i][j];
}
}
int now = 0;
loop(i,0,n){
loop(j,0,m){
if(c[i][j] == 'R' && c[i][j+1] == 'G' && c[i][j+2] == 'W'){
now++;
check(i, j, now);
check(i, j + 1, now);
check(i, j + 2, now);
can[now] = true;
}
if(c[i][j] == 'R' && c[i+1][j] == 'G' && c[i+2][j] == 'W'){
now++;
check(i, j, now);
check(i + 1, j, now);
check(i + 2, j, now);
can[now] = true;
}
}
}
unisort(EV);
for(auto &i:EV){
E[i.ff].pb(i.ss);
E[i.ss].pb(i.ff);
// opa(i.ff) op(i.ss);
}
int ans = 0;
loop(i,1,now + 1){
if((!vis[i]) && can[i]){
int sz = 0, black = 0;
dfs(i, sz, true, black);
ans += max(black, sz - black);
}
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
215892 KB |
Output is correct |
2 |
Correct |
47 ms |
216152 KB |
Output is correct |
3 |
Correct |
47 ms |
215860 KB |
Output is correct |
4 |
Correct |
47 ms |
215892 KB |
Output is correct |
5 |
Correct |
48 ms |
215888 KB |
Output is correct |
6 |
Correct |
47 ms |
215888 KB |
Output is correct |
7 |
Correct |
48 ms |
216100 KB |
Output is correct |
8 |
Correct |
48 ms |
215888 KB |
Output is correct |
9 |
Correct |
46 ms |
215872 KB |
Output is correct |
10 |
Correct |
47 ms |
215888 KB |
Output is correct |
11 |
Correct |
47 ms |
215900 KB |
Output is correct |
12 |
Correct |
52 ms |
215896 KB |
Output is correct |
13 |
Correct |
47 ms |
215908 KB |
Output is correct |
14 |
Correct |
47 ms |
215904 KB |
Output is correct |
15 |
Correct |
46 ms |
215916 KB |
Output is correct |
16 |
Correct |
47 ms |
215888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
215892 KB |
Output is correct |
2 |
Correct |
47 ms |
216152 KB |
Output is correct |
3 |
Correct |
47 ms |
215860 KB |
Output is correct |
4 |
Correct |
47 ms |
215892 KB |
Output is correct |
5 |
Correct |
48 ms |
215888 KB |
Output is correct |
6 |
Correct |
47 ms |
215888 KB |
Output is correct |
7 |
Correct |
48 ms |
216100 KB |
Output is correct |
8 |
Correct |
48 ms |
215888 KB |
Output is correct |
9 |
Correct |
46 ms |
215872 KB |
Output is correct |
10 |
Correct |
47 ms |
215888 KB |
Output is correct |
11 |
Correct |
47 ms |
215900 KB |
Output is correct |
12 |
Correct |
52 ms |
215896 KB |
Output is correct |
13 |
Correct |
47 ms |
215908 KB |
Output is correct |
14 |
Correct |
47 ms |
215904 KB |
Output is correct |
15 |
Correct |
46 ms |
215916 KB |
Output is correct |
16 |
Correct |
47 ms |
215888 KB |
Output is correct |
17 |
Correct |
48 ms |
215840 KB |
Output is correct |
18 |
Correct |
46 ms |
215920 KB |
Output is correct |
19 |
Correct |
46 ms |
215892 KB |
Output is correct |
20 |
Correct |
48 ms |
215720 KB |
Output is correct |
21 |
Correct |
45 ms |
215888 KB |
Output is correct |
22 |
Correct |
46 ms |
215896 KB |
Output is correct |
23 |
Correct |
47 ms |
216148 KB |
Output is correct |
24 |
Correct |
45 ms |
215744 KB |
Output is correct |
25 |
Correct |
46 ms |
215840 KB |
Output is correct |
26 |
Correct |
47 ms |
215732 KB |
Output is correct |
27 |
Correct |
46 ms |
215896 KB |
Output is correct |
28 |
Correct |
47 ms |
215888 KB |
Output is correct |
29 |
Correct |
47 ms |
215892 KB |
Output is correct |
30 |
Correct |
47 ms |
215888 KB |
Output is correct |
31 |
Correct |
50 ms |
215892 KB |
Output is correct |
32 |
Correct |
47 ms |
215892 KB |
Output is correct |
33 |
Correct |
47 ms |
215944 KB |
Output is correct |
34 |
Incorrect |
46 ms |
215888 KB |
Output isn't correct |
35 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
215892 KB |
Output is correct |
2 |
Correct |
47 ms |
216152 KB |
Output is correct |
3 |
Correct |
47 ms |
215860 KB |
Output is correct |
4 |
Correct |
47 ms |
215892 KB |
Output is correct |
5 |
Correct |
48 ms |
215888 KB |
Output is correct |
6 |
Correct |
47 ms |
215888 KB |
Output is correct |
7 |
Correct |
48 ms |
216100 KB |
Output is correct |
8 |
Correct |
48 ms |
215888 KB |
Output is correct |
9 |
Correct |
46 ms |
215872 KB |
Output is correct |
10 |
Correct |
47 ms |
215888 KB |
Output is correct |
11 |
Correct |
47 ms |
215900 KB |
Output is correct |
12 |
Correct |
52 ms |
215896 KB |
Output is correct |
13 |
Correct |
47 ms |
215908 KB |
Output is correct |
14 |
Correct |
47 ms |
215904 KB |
Output is correct |
15 |
Correct |
46 ms |
215916 KB |
Output is correct |
16 |
Correct |
47 ms |
215888 KB |
Output is correct |
17 |
Correct |
48 ms |
215840 KB |
Output is correct |
18 |
Correct |
46 ms |
215920 KB |
Output is correct |
19 |
Correct |
46 ms |
215892 KB |
Output is correct |
20 |
Correct |
48 ms |
215720 KB |
Output is correct |
21 |
Correct |
45 ms |
215888 KB |
Output is correct |
22 |
Correct |
46 ms |
215896 KB |
Output is correct |
23 |
Correct |
47 ms |
216148 KB |
Output is correct |
24 |
Correct |
45 ms |
215744 KB |
Output is correct |
25 |
Correct |
46 ms |
215840 KB |
Output is correct |
26 |
Correct |
47 ms |
215732 KB |
Output is correct |
27 |
Correct |
46 ms |
215896 KB |
Output is correct |
28 |
Correct |
47 ms |
215888 KB |
Output is correct |
29 |
Correct |
47 ms |
215892 KB |
Output is correct |
30 |
Correct |
47 ms |
215888 KB |
Output is correct |
31 |
Correct |
50 ms |
215892 KB |
Output is correct |
32 |
Correct |
47 ms |
215892 KB |
Output is correct |
33 |
Correct |
47 ms |
215944 KB |
Output is correct |
34 |
Incorrect |
46 ms |
215888 KB |
Output isn't correct |
35 |
Halted |
0 ms |
0 KB |
- |