Submission #1306161

#TimeUsernameProblemLanguageResultExecution timeMemory
1306161duyanhchupapiDango Maker (JOI18_dango_maker)C++20
33 / 100
490 ms276824 KiB
#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = 3003;
int n, m, _n, _m, id[N][N];
int seen[N * N], iter = 0;
int dist[N * N], matchL[N * N], matchR[N * N];
vector <int> g[N * N];
char a[N][N];
bool col[N][N];
bool stick(char A, char B, char C) {
	if (A == 'R' && B == 'G' && C == 'W') return true;
	return false;
}

bool dfs(int u) {
    if(seen[u] == iter) return 0;
    seen[u] = iter;

    for(int v : g[u])
        if(matchR[v] == -1) {
            matchL[u] = v; matchR[v] = u;
            return 1;
        }

    for(int v : g[u])
        if(dist[matchR[v]] == dist[u] + 1 && dfs(matchR[v])) {
            matchL[u] = v; matchR[v] = u;
            return 1;
        }

    return 0;
}

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0);
	// freopen(".INP", "r", stdin);
	// freopen(".OUT", "w", stdout);
	cin >> _n >> _m;

	for (int i=1;i<=_n;++i) 
		for (int j=1;j<=_m;++j) cin >> a[i][j];
		
	for (int i=1;i<=_n;++i) {
		for (int j=1;j<=_m;++j) {
			if (stick(a[i][j], a[i + 1][j], a[i + 2][j])) {
				col[i][j] = 1;
				id[i][j] = ++n;
			}
			
			if (stick(a[i][j], a[i][j + 1], a[i][j + 2])) {
				m++;
				if (col[i][j]) g[id[i][j]].push_back(m);
				if (col[i - 1][j + 1]) g[id[i - 1][j + 1]].push_back(m);
				if (i != 1 && col[i - 2][j + 2]) g[id[i - 2][j + 2]].push_back(m);
 			}

		}
	} 
	
	fill(matchL + 1, matchL + n + 1, -1);
    fill(matchR + 1, matchR + m + 1, -1);
    int ans = 0;
    while(1) {
        queue<int> q;
        for(int u = 1; u <= n; ++u) {
            if(matchL[u] == -1) dist[u] = 0, q.push(u);
            else dist[u] = -1;
        }

        while(q.size()) {
            int u = q.front(); q.pop();
            for(int v : g[u]) {
                if(matchR[v] != -1 && dist[matchR[v]] == -1) {
                    dist[matchR[v]] = dist[u] + 1;
                    q.push(matchR[v]);
                }
            }
        }

        int add = 0;
        ++iter;
        for(int u = 1; u <= n; ++u) {
            if(matchL[u] == -1) add += dfs(u);
        }
        if(add == 0) break;
        ans += add;
    }
	
	cout << n + m - ans;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...