Submission #164507

#TimeUsernameProblemLanguageResultExecution timeMemory
164507balbitDango Maker (JOI18_dango_maker)C++14
33 / 100
2079 ms177204 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i<b; i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i = n-1; i>=0; i--)
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define pb push_back
#ifdef BALBIT
#define IOS()
#define bug(x) cerr<<__LINE__<<' '<<#x<<": "<<x<<endl
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(x)
#endif

const ll mod = 1e9+7;
const int maxn = 3e3+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iinf = 0x3f3f3f3f;

int mx[maxn*maxn/3],my[maxn*maxn/3];
bool vy[maxn*maxn/3];
vector<int> edge[maxn*maxn/3];

int N, M;
int greedy_matching()
{
    int c = 0;
    for (int x=0; x<N; ++x) {
        if (mx[x] == -1) {
            for (auto y : edge[x]) {
                if (my[y] == -1) {
                        mx[x] = y; my[y] = x;
                        c++;
                        break;
                }
            }
        }
    }
    return c;
}
 
bool DFS(int x)
{
    for (auto y : edge[x]) {
        if (!vy[y]) {
            vy[y] = true;
            if (my[y] == -1 || DFS(my[y]))
            {
                mx[x] = y; my[y] = x;
                return true;
            }
        }
    }
    return false;
}

int bipartite_matching()
{
    memset(mx, -1, sizeof(mx));
    memset(my, -1, sizeof(my));
 
    int c = greedy_matching();
 
    for (int x=0; x<N; ++x)
        if (mx[x] == -1)  
        {
            memset(vy, false, sizeof(vy));
            if (DFS(x)) c++;
        }
    return c;
}

char grd[maxn][maxn];

int idup[maxn][maxn];
int idrt[maxn][maxn];


signed main(){
	IOS();
	int n, m; cin>>n>>m;
//	assert(n!=3000 || m!=3000);
	REP(i,n) REP(j,m) cin>>grd[i][j];
	int nup = 0, nrt = 0;
	memset(idup, -1, sizeof(idup));
	memset(idrt, -1, sizeof(idrt));
	REP(i,n)REP(j,m){

		if(grd[i][j]=='G'){
			if (i && i!=n-1 && grd[i-1][j] == 'R' && grd[i+1][j]=='W' ) {
				idup[i][j] = nup++;
			}
			if (j && j!=m-1 && grd[i][j-1] == 'R' && grd[i][j+1]=='W' ) {
				idrt[i][j] = nrt ++;
			}
		}
	}

	N = nup; M = nrt;
//	Dinic dd (N,S,T);
	REP(i,n) REP(j,m){
		if(idup[i][j]!=-1){
//			cout<<i<<' '<<j<<' '<<idup[i][j]<<endl;

			if(idrt[i][j] != -1) {
				edge[idup[i][j]].pb(idrt[i][j]);
			}
			if(i && idrt[i-1][j+1]!=-1){
				edge[idup[i][j]].pb(idrt[i-1][j+1]);
			}
			if(j && idrt[i+1][j-1]!=-1){
				edge[idup[i][j]].pb(idrt[i+1][j-1]);
			}
		}

	}
	cout<<nup + nrt - bipartite_matching() << endl;
	
}




#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...