Submission #584591

#	Time	Username	Problem	Language	Result	Execution time	Memory
584591		8e7	Rectangles (IOI19_rect)	C++17	0 / 100	128 ms	23200 KiB

rect

#include "rect.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();	
	vector<vector<bool> > vis(n, vector<bool>(m, 0));

	ll ret = 0;
	for (int i = 1;i < n-1;i++) {
		for (int j = 1;j < m-1;j++) {
			if (!vis[i][j] && a[i][j] == 0) {
				//debug(i, j);
				queue<pii> que;
				bool good = 1;	
				que.push({i, j});
				int cnt = 0;
				int xmin = n+1, xmax = 0, ymin = m+1, ymax = 0;
				while (que.size()) {
					pii cur = que.front();que.pop();
					vis[cur.ff][cur.ss] = 1;
					cnt++;
					xmin = min(xmin, cur.ff);
					xmax = max(xmax, cur.ff);
					ymin = min(ymin, cur.ss);
					ymax = max(ymax, cur.ss);
					for (int d = 0;d < 4;d++) {
						int nx = cur.ff + dir[d][0], ny = cur.ss + dir[d][1];
						if (!vis[nx][ny] && a[nx][ny] == 0) {
							if (nx <= 0 || nx >= n - 1 || ny <= 0 || ny >= m - 1) {
								good = 0;
								break;
							} else {
								vis[nx][ny] = 1;
								que.push({nx, ny});
							}
						}
					}
				}
				//debug(i, j, cnt, (xmax - xmin+1) * (ymax - ymin+1));
				if (cnt == (xmax - xmin+1) * (ymax - ymin+1) && good) {
					ret++;
				}
			}
		}
	}
	return ret;
}

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