Submission #805454

#	Time	Username	Problem	Language	Result	Execution time	Memory
805454		faruk	Rectangles (IOI19_rect)	C++17	13 / 100	417 ms	306060 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<int> xs;
vector<int> ys;
vector<vector<int> > a;
vector<vector<bool> > b;
int n, m;
void dfs(int x, int y) {
	if (x == n || y == m || x == -1 || y == -1)
		return;
	if (a[x][y] == 1 || b[x][y])
		return;
	xs.push_back(x);
	ys.push_back(y);
	b[x][y] = true;

	dfs(x - 1, y);
	dfs(x + 1, y);
	dfs(x, y + 1);
	dfs(x, y - 1);
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	::a = a;
	int cnt = 0;
	n = a.size();
	m = a[0].size();
	b.resize(n, vector<bool>(m));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (b[i][j] || a[i][j] == 1)
				continue;
			dfs(i, j);
			int minx = *min_element(all(xs));
			int maxx = *max_element(all(xs));
			int miny = *min_element(all(ys));
			int maxy = *max_element(all(ys));
			int siz = xs.size();
			xs.clear();
			ys.clear();
			if (min(minx, miny) == 0)
				continue;
			if (maxx == n -1 || maxy == m - 1)
				continue;
			if (siz == (maxx - minx + 1) * (maxy - miny + 1))
				cnt++;
		}
	}
	return cnt;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28