oj.uz

Submission #97961

# Submission time Handle Problem Language Result Execution time Memory
97961 2019-02-19T16:35:31 Z Anai Dango Maker (JOI18_dango_maker) C++14
0 / 100
 237 ms 213624 KB 
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int N = 3005;

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

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

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

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

	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] == 'G';
		bool ver = mx[i - 2][j] == 'R' && mx[i - 1][j] == 'G';
		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)); }

	mx.clear();
	mx.shrink_to_fit();

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

	cout << ant << endl;

//	cerr << (sizeof(g) + sizeof(st) + sizeof(dr) + sizeof(f)) / 1024 / 1024 << endl;

	return 0; }

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 213496 KB Output is correct
2 Correct 206 ms 213556 KB Output is correct
3 Correct 202 ms 213496 KB Output is correct
4 Correct 237 ms 213496 KB Output is correct
5 Correct 230 ms 213476 KB Output is correct
6 Correct 203 ms 213624 KB Output is correct
7 Correct 193 ms 213496 KB Output is correct
8 Incorrect 191 ms 213496 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 213496 KB Output is correct
2 Correct 206 ms 213556 KB Output is correct
3 Correct 202 ms 213496 KB Output is correct
4 Correct 237 ms 213496 KB Output is correct
5 Correct 230 ms 213476 KB Output is correct
6 Correct 203 ms 213624 KB Output is correct
7 Correct 193 ms 213496 KB Output is correct
8 Incorrect 191 ms 213496 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 213496 KB Output is correct
2 Correct 206 ms 213556 KB Output is correct
3 Correct 202 ms 213496 KB Output is correct
4 Correct 237 ms 213496 KB Output is correct
5 Correct 230 ms 213476 KB Output is correct
6 Correct 203 ms 213624 KB Output is correct
7 Correct 193 ms 213496 KB Output is correct
8 Incorrect 191 ms 213496 KB Output isn't correct
9 Halted 0 ms 0 KB -