#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
cout<<a<<" ",debug(b...);
}
const int N=3e3+7;
const int INF=1e18;
char c[N][N];
int col[N][N];
int row[N][N];
const int M=3e6+7;
vector<int> v3[M];
int color[N];
int w;
int b;
void add_edge(int a,int b){
v3[a].eb(b);
v3[b].eb(a);
}
void dfs(int x,int pnt=1){
if(color[x]) return;
color[x]=pnt;
if(pnt==1) w++;
else b++;
for(int i:v3[x]){
dfs(i,-pnt);
}
}
signed main(){
quick
int n,m;
cin>>n>>m;
rep(i,1,n){
rep(j,1,m) cin>>c[i][j];
}
int Cc=0;
int Cr=0;
rep(i,1,n){
rep(j,1,m){
if(j+2<=m&&c[i][j]=='R'&&c[i][j+1]=='G'&&c[i][j+2]=='W'){
++Cc;
rep(jx,j,j+2){
col[i][jx]=Cc;
}
}
if(i+2<=n&&c[i][j]=='R'&&c[i+1][j]=='G'&&c[i+2][j]=='W'){
++Cr;
rep(ix,i,i+2){
row[ix][j]=Cr;
}
}
}
}
rep(i,1,n){
rep(j,1,m){
if(col[i][j]&&row[i][j]){
add_edge(col[i][j],row[i][j]+Cc);
}
}
}
int n2=Cc+Cr;
int ans=0;
rep(i,1,n2){
if(!color[i]){
b=w=0;
dfs(i,1);
ans+=max(b,w);
}
}
cout<<ans<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
70732 KB |
Output is correct |
2 |
Correct |
38 ms |
70732 KB |
Output is correct |
3 |
Correct |
37 ms |
70780 KB |
Output is correct |
4 |
Correct |
42 ms |
70772 KB |
Output is correct |
5 |
Correct |
44 ms |
70732 KB |
Output is correct |
6 |
Correct |
39 ms |
70740 KB |
Output is correct |
7 |
Correct |
38 ms |
70804 KB |
Output is correct |
8 |
Correct |
42 ms |
70764 KB |
Output is correct |
9 |
Correct |
38 ms |
70788 KB |
Output is correct |
10 |
Correct |
39 ms |
70696 KB |
Output is correct |
11 |
Correct |
38 ms |
70724 KB |
Output is correct |
12 |
Correct |
38 ms |
70740 KB |
Output is correct |
13 |
Correct |
38 ms |
70768 KB |
Output is correct |
14 |
Correct |
46 ms |
70848 KB |
Output is correct |
15 |
Correct |
39 ms |
70708 KB |
Output is correct |
16 |
Correct |
40 ms |
70768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
70732 KB |
Output is correct |
2 |
Correct |
38 ms |
70732 KB |
Output is correct |
3 |
Correct |
37 ms |
70780 KB |
Output is correct |
4 |
Correct |
42 ms |
70772 KB |
Output is correct |
5 |
Correct |
44 ms |
70732 KB |
Output is correct |
6 |
Correct |
39 ms |
70740 KB |
Output is correct |
7 |
Correct |
38 ms |
70804 KB |
Output is correct |
8 |
Correct |
42 ms |
70764 KB |
Output is correct |
9 |
Correct |
38 ms |
70788 KB |
Output is correct |
10 |
Correct |
39 ms |
70696 KB |
Output is correct |
11 |
Correct |
38 ms |
70724 KB |
Output is correct |
12 |
Correct |
38 ms |
70740 KB |
Output is correct |
13 |
Correct |
38 ms |
70768 KB |
Output is correct |
14 |
Correct |
46 ms |
70848 KB |
Output is correct |
15 |
Correct |
39 ms |
70708 KB |
Output is correct |
16 |
Correct |
40 ms |
70768 KB |
Output is correct |
17 |
Correct |
38 ms |
70744 KB |
Output is correct |
18 |
Correct |
40 ms |
70732 KB |
Output is correct |
19 |
Correct |
40 ms |
70828 KB |
Output is correct |
20 |
Correct |
37 ms |
70864 KB |
Output is correct |
21 |
Correct |
44 ms |
70852 KB |
Output is correct |
22 |
Correct |
48 ms |
70840 KB |
Output is correct |
23 |
Correct |
37 ms |
70740 KB |
Output is correct |
24 |
Correct |
38 ms |
70732 KB |
Output is correct |
25 |
Correct |
41 ms |
70740 KB |
Output is correct |
26 |
Correct |
38 ms |
70736 KB |
Output is correct |
27 |
Correct |
41 ms |
70800 KB |
Output is correct |
28 |
Correct |
41 ms |
70952 KB |
Output is correct |
29 |
Correct |
39 ms |
70884 KB |
Output is correct |
30 |
Correct |
38 ms |
70736 KB |
Output is correct |
31 |
Correct |
37 ms |
70760 KB |
Output is correct |
32 |
Correct |
45 ms |
70732 KB |
Output is correct |
33 |
Correct |
35 ms |
70776 KB |
Output is correct |
34 |
Incorrect |
37 ms |
70812 KB |
Output isn't correct |
35 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
70732 KB |
Output is correct |
2 |
Correct |
38 ms |
70732 KB |
Output is correct |
3 |
Correct |
37 ms |
70780 KB |
Output is correct |
4 |
Correct |
42 ms |
70772 KB |
Output is correct |
5 |
Correct |
44 ms |
70732 KB |
Output is correct |
6 |
Correct |
39 ms |
70740 KB |
Output is correct |
7 |
Correct |
38 ms |
70804 KB |
Output is correct |
8 |
Correct |
42 ms |
70764 KB |
Output is correct |
9 |
Correct |
38 ms |
70788 KB |
Output is correct |
10 |
Correct |
39 ms |
70696 KB |
Output is correct |
11 |
Correct |
38 ms |
70724 KB |
Output is correct |
12 |
Correct |
38 ms |
70740 KB |
Output is correct |
13 |
Correct |
38 ms |
70768 KB |
Output is correct |
14 |
Correct |
46 ms |
70848 KB |
Output is correct |
15 |
Correct |
39 ms |
70708 KB |
Output is correct |
16 |
Correct |
40 ms |
70768 KB |
Output is correct |
17 |
Correct |
38 ms |
70744 KB |
Output is correct |
18 |
Correct |
40 ms |
70732 KB |
Output is correct |
19 |
Correct |
40 ms |
70828 KB |
Output is correct |
20 |
Correct |
37 ms |
70864 KB |
Output is correct |
21 |
Correct |
44 ms |
70852 KB |
Output is correct |
22 |
Correct |
48 ms |
70840 KB |
Output is correct |
23 |
Correct |
37 ms |
70740 KB |
Output is correct |
24 |
Correct |
38 ms |
70732 KB |
Output is correct |
25 |
Correct |
41 ms |
70740 KB |
Output is correct |
26 |
Correct |
38 ms |
70736 KB |
Output is correct |
27 |
Correct |
41 ms |
70800 KB |
Output is correct |
28 |
Correct |
41 ms |
70952 KB |
Output is correct |
29 |
Correct |
39 ms |
70884 KB |
Output is correct |
30 |
Correct |
38 ms |
70736 KB |
Output is correct |
31 |
Correct |
37 ms |
70760 KB |
Output is correct |
32 |
Correct |
45 ms |
70732 KB |
Output is correct |
33 |
Correct |
35 ms |
70776 KB |
Output is correct |
34 |
Incorrect |
37 ms |
70812 KB |
Output isn't correct |
35 |
Halted |
0 ms |
0 KB |
- |