Submission #1332970

#TimeUsernameProblemLanguageResultExecution timeMemory
1332970WarinchaiDango Maker (JOI18_dango_maker)C++20
13 / 100
76 ms1440 KiB
#include<bits/stdc++.h>
using namespace std;

string s[3005];
vector<int>adj[18000005];
int n,m;
int can[3005][3005];
int can2[3005][3005];
int pp[18000005];

int g(int x,int y){
    return x*m+y;
}

int val[5],vis[18000005];

void dfs(int u,int par){
    val[par]++;
    pp[u]=par;
    for(auto x:adj[u]){
        if(vis[x]){
            assert((pp[u]==(pp[x]^1)));
            continue;
        }
        vis[x]=1;
        dfs(x,par^1);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(j+2<m){
                if(s[i][j]=='R'&&s[i][j+1]=='G'&&s[i][j+2]=='W'){
                    can[i][j]=1;
                    if(i+2<n&&s[i+1][j]=='G'&&s[i+2][j]=='W')adj[g(i,j)].push_back(n*m+g(i,j)),adj[n*m+g(i,j)].push_back(g(i,j));
                    if(i+1<n&&i-1>=0&&s[i-1][j+1]=='R'&&s[i+1][j+1]=='W')adj[g(i,j)].push_back(n*m+g(i-1,j+1)),adj[n*m+g(i-1,j+1)].push_back(g(i,j));
                    if(i-2>=0&&s[i-2][j+2]=='R'&&s[i-1][j+2]=='G')adj[g(i,j)].push_back(n*m+g(i-2,j+2)),adj[n*m+g(i-2,j+2)].push_back(g(i,j));
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i+2<n){
                if(s[i][j]=='R'&&s[i+1][j]=='G'&&s[i+2][j]=='W'){
                    can2[i][j]=1;
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        if(!vis[g(i,j)]&&can[i][j]){
            val[0]=val[1]=0;
            vis[g(i,j)]=1;
            dfs(g(i,j),0);
            ans+=max(val[0],val[1]);
        }
        if(!vis[g(i,j)+n*m]&&can2[i][j]){
            val[0]=val[1]=0;
            vis[g(i,j)+n*m]=1;
            dfs(g(i,j)+n*m,0);
            ans+=max(val[0],val[1]);
        }
    }
    cout<<ans<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...