Submission #682042

#	Time	Username	Problem	Language	Result	Execution time	Memory
682042		ethening	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	443 ms	262144 KiB

dango_maker

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

// RGW
int n, m;
string s[3005];
int a[3005][3005], b[3005][3005];
vector<int> va[3000005];
int ma[3000005], mb[3000005];
bool visitb[3000005];
int cnt, cnt2;

stack<int> clrS;

bool dfs(int cur) {
	for (int nxt : va[cur]) {
		if (!visitb[nxt]) {
			visitb[nxt] = true;
			clrS.push(nxt);
			if (mb[nxt] == -1 || dfs(mb[nxt])) {
				ma[cur] = nxt;
				mb[nxt] = cur;
				return true;
			}
		}
	}
	return false;
}


int bipartite_matching() {
	memset(ma, -1, sizeof(ma));
	memset(mb, -1, sizeof(mb));
	int ret = 0;
	for (int i = 1; i <= cnt; i++) {
		while (!clrS.empty()) {
			visitb[clrS.top()] = false;
			clrS.pop();
		}
		if (dfs(i)) ++ret;
	}
	return ret;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	cnt = cnt2 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (s[i][j] != 'R') continue;
			if (j + 2 < m) {
				if (s[i][j + 1] == 'G' && s[i][j + 2] == 'W') {
					++cnt;
					a[i][j] = cnt;
					a[i][j + 1] = cnt;
					a[i][j + 2] = cnt;
				}
			}
			if (i + 2 < n) {
				if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') {
					++cnt2;
					b[i][j]= cnt2;
					b[i + 1][j]= cnt2;
					b[i + 2][j]= cnt2;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] != 0 && b[i][j] != 0) {
				va[a[i][j]].push_back(b[i][j]);
			}
		}
	}
	cout << cnt + cnt2 - bipartite_matching() << endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67