oj.uz

Submission #97953

# Submission time Handle Problem Language Result Execution time Memory
97953 2019-02-19T16:15:38 Z Anai Dango Maker (JOI18_dango_maker) C++14
0 / 100
 213 ms 212512 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3005;


vector<int> g[N * N];
int st[N * N], dr[N * N], f[N * N];

vector<string> mx;
int n, m, fp;

static int cod(int l, int c) {
	return 1 + l * m + c; }

static bool match(int u) {
	if (f[u] == fp)
		return false;
	f[u] = fp;

	for (auto v: g[u]) if (!dr[v]) {
		st[u] = v;
		dr[v] = u;
		return true; }

	for (auto v: g[u]) if (match(dr[v])) {
		st[u] = v;
		dr[v] = u;
		return true; }
	return false;}


int main() {
#ifdef HOME
	freopen("joi_dango.in", "r", stdin);
	freopen("joi_dango.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int add, ant;

	cin >> n >> m;
	mx.resize(n);
	for (auto &line: mx)
		cin >> line;

	ant = 0;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j) if (mx[i][j] == 'R') {
		bool hor = j + 2 < m ? (mx[i][j + 1] == 'G' && mx[i][j + 2] == 'W') : 0;
		bool ver = i + 2 < n ? (mx[i + 1][j] == 'G' && mx[i + 2][j] == 'W') : 0;

		ant+= int(hor) + int(ver);
		if (hor && ver)
			g[cod(i, j)].push_back(cod(i, j)); }

	for (int i = 2; i < n; ++i)
	for (int j = 2; j < m; ++j) if (mx[i][j] == 'W') {
		bool hor = mx[i][j - 2] == 'R' && mx[i][j - 1] == 'W';
		bool ver = mx[i - 2][j] == 'R' && mx[i - 1][j] == 'W';
		if (hor && ver)
			g[cod(i - 2, j)].push_back(cod(i, j - 2)); }
	
	

	for (int i = 1; i < n - 1; ++i)
	for (int j = 1; j < m - 1; ++j) if (mx[i][j] == 'G') {
		if (mx[i - 1][j] == 'R' && mx[i + 1][j] == 'W')
		if (mx[i][j - 1] == 'R' && mx[i][j + 1] == 'W')
			g[cod(i - 1, j)].push_back(cod(i, j - 1)); }

	do {
		fp+= 1;
		add = 0;
		for (int i = 1; i <= n * m; ++i)
			if (!st[i] && f[i] != fp)
				add+= int(match(i));
		ant-= add; }
	while (add);

	cout << ant << endl;

	return 0; }

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 212344 KB Output is correct
2 Correct 208 ms 212512 KB Output is correct
3 Correct 196 ms 212472 KB Output is correct
4 Correct 213 ms 212472 KB Output is correct
5 Correct 197 ms 212400 KB Output is correct
6 Incorrect 197 ms 212420 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 212344 KB Output is correct
2 Correct 208 ms 212512 KB Output is correct
3 Correct 196 ms 212472 KB Output is correct
4 Correct 213 ms 212472 KB Output is correct
5 Correct 197 ms 212400 KB Output is correct
6 Incorrect 197 ms 212420 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 212344 KB Output is correct
2 Correct 208 ms 212512 KB Output is correct
3 Correct 196 ms 212472 KB Output is correct
4 Correct 213 ms 212472 KB Output is correct
5 Correct 197 ms 212400 KB Output is correct
6 Incorrect 197 ms 212420 KB Output isn't correct
7 Halted 0 ms 0 KB -