oj.uz

Submission #97977

# Submission time Handle Problem Language Result Execution time Memory
97977 2019-02-19T16:59:32 Z Anai Dango Maker (JOI18_dango_maker) C++14
0 / 100
 2000 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];
vector<int> st, dr;
bitset<N * N> f;

vector<int> used;
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])
		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)
			used.push_back(cod(i, j));
		if (hor && ver) {
			g[used.size() - 1].push_back(used.size() - 1); } }

	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) {
			int h = lower_bound(begin(used), end(used), cod(i - 2, j)) - begin(used);
			int v = lower_bound(begin(used), end(used), cod(i, j - 2)) - begin(used);
			g[v].push_back(h); } }


	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') {
			int h = lower_bound(begin(used), end(used), cod(i - 1, j)) - begin(used);
			int v = lower_bound(begin(used), end(used), cod(i, j - 1)) - begin(used);
			g[v].push_back(h); } }

	mx.clear();
	mx.shrink_to_fit();
	st.resize(used.size() + 5);
	dr.resize(used.size() + 5);

	do {
		f = 0;
		add = 0;
		for (int i = 0; i < used.size(); ++i)
			if (!st[i] && !f[i])
				add+= int(match(i));
		ant-= add; }
	while (add);

	cout << ant << endl;

	return 0; }

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < used.size(); ++i)
                   ~~^~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 213496 KB Output is correct
2 Correct 223 ms 213520 KB Output is correct
3 Correct 216 ms 213624 KB Output is correct
4 Correct 204 ms 213568 KB Output is correct
5 Correct 223 ms 213528 KB Output is correct
6 Correct 215 ms 213496 KB Output is correct
7 Correct 225 ms 213420 KB Output is correct
8 Execution timed out 2065 ms 213528 KB Time limit exceeded
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 223 ms 213520 KB Output is correct
3 Correct 216 ms 213624 KB Output is correct
4 Correct 204 ms 213568 KB Output is correct
5 Correct 223 ms 213528 KB Output is correct
6 Correct 215 ms 213496 KB Output is correct
7 Correct 225 ms 213420 KB Output is correct
8 Execution timed out 2065 ms 213528 KB Time limit exceeded
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 223 ms 213520 KB Output is correct
3 Correct 216 ms 213624 KB Output is correct
4 Correct 204 ms 213568 KB Output is correct
5 Correct 223 ms 213528 KB Output is correct
6 Correct 215 ms 213496 KB Output is correct
7 Correct 225 ms 213420 KB Output is correct
8 Execution timed out 2065 ms 213528 KB Time limit exceeded
9 Halted 0 ms 0 KB -