oj.uz

Submission #97974

# Submission time Handle Problem Language Result Execution time Memory
97974 2019-02-19T16:56:16 Z Anai Dango Maker (JOI18_dango_maker) C++14
13 / 100
 230 ms 213600 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) {
			ant-= 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:91:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < used.size(); ++i)
                   ~~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 213548 KB Output is correct
2 Correct 208 ms 213472 KB Output is correct
3 Correct 230 ms 213408 KB Output is correct
4 Correct 208 ms 213496 KB Output is correct
5 Correct 207 ms 213496 KB Output is correct
6 Correct 187 ms 213424 KB Output is correct
7 Correct 192 ms 213496 KB Output is correct
8 Correct 209 ms 213496 KB Output is correct
9 Correct 194 ms 213600 KB Output is correct
10 Correct 189 ms 213496 KB Output is correct
11 Correct 199 ms 213468 KB Output is correct
12 Correct 212 ms 213576 KB Output is correct
13 Correct 199 ms 213512 KB Output is correct
14 Correct 186 ms 213500 KB Output is correct
15 Correct 186 ms 213496 KB Output is correct
16 Correct 188 ms 213496 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 213548 KB Output is correct
2 Correct 208 ms 213472 KB Output is correct
3 Correct 230 ms 213408 KB Output is correct
4 Correct 208 ms 213496 KB Output is correct
5 Correct 207 ms 213496 KB Output is correct
6 Correct 187 ms 213424 KB Output is correct
7 Correct 192 ms 213496 KB Output is correct
8 Correct 209 ms 213496 KB Output is correct
9 Correct 194 ms 213600 KB Output is correct
10 Correct 189 ms 213496 KB Output is correct
11 Correct 199 ms 213468 KB Output is correct
12 Correct 212 ms 213576 KB Output is correct
13 Correct 199 ms 213512 KB Output is correct
14 Correct 186 ms 213500 KB Output is correct
15 Correct 186 ms 213496 KB Output is correct
16 Correct 188 ms 213496 KB Output is correct
17 Correct 211 ms 213412 KB Output is correct
18 Correct 193 ms 213544 KB Output is correct
19 Incorrect 189 ms 213496 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 213548 KB Output is correct
2 Correct 208 ms 213472 KB Output is correct
3 Correct 230 ms 213408 KB Output is correct
4 Correct 208 ms 213496 KB Output is correct
5 Correct 207 ms 213496 KB Output is correct
6 Correct 187 ms 213424 KB Output is correct
7 Correct 192 ms 213496 KB Output is correct
8 Correct 209 ms 213496 KB Output is correct
9 Correct 194 ms 213600 KB Output is correct
10 Correct 189 ms 213496 KB Output is correct
11 Correct 199 ms 213468 KB Output is correct
12 Correct 212 ms 213576 KB Output is correct
13 Correct 199 ms 213512 KB Output is correct
14 Correct 186 ms 213500 KB Output is correct
15 Correct 186 ms 213496 KB Output is correct
16 Correct 188 ms 213496 KB Output is correct
17 Correct 211 ms 213412 KB Output is correct
18 Correct 193 ms 213544 KB Output is correct
19 Incorrect 189 ms 213496 KB Output isn't correct
20 Halted 0 ms 0 KB -