Submission #1281654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281654		nicolo_010	Rectangles (IOI19_rect)	C++20	13 / 100	209 ms	50468 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, m;

bool valid(int x, int y) {
	if (x >= 0 && x<n && y >= 0 && y < m) return true;
	else return false;
}

ll count_rectangles(vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();
	vector<int> dx = {1, 0, -1, 0};
	vector<int> dy = {0, 1, 0, -1};
	vector<vector<bool>> vis(n, vector<bool>(m, false));
	/*vector<vector<int>> rows(n, vector<int>(m, 0));
	for (int i=0; i<n; i++) {
		rows[i][0] = a[i][0];
		for (int j=1; j<m; j++) {
			rows[i][j] = rows[i][j-1] + a[i][j];
		}
	}
	vector<vector<int>> col(m, vector<int>(n, 0));
	for (int i=0; i<m; i++) {
		col[i][0] = a[0][i];
		for (int j=1; j<n; j++) {
			col[i][j] = a[j][i] + col[i][j-1];
		}
	}*/
	ll ans=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) {
				vis[i][j] = true;
				int mnx = i;
				int mxx = i;
				int mny = j;
				int mxy = j;
				queue<pii> q;
				q.push({i, j});
				int cnt=0;
				while (!q.empty()) {
					int ni = q.front().first;
					int nj = q.front().second;
					cnt++;
					q.pop();
					for (int k=0; k<4; k++) {
						int x = ni+dx[k];
						int y = nj+dy[k];
						if (valid(x, y) && a[x][y] == 0 && !vis[x][y]) {
							vis[x][y] = true;
							mxx = max(mxx, x);
							mnx = min(mnx, x);
							mny = min(mny, y);
							mxy = max(mxy, y);
							q.push({x, y});
						}
					}
				}
				if ((mxx-mnx+1) * (mxy-mny+1) == cnt && mny != 0 && mnx != 0 && mxx != n-1 && mxy != m-1) {
					ans++;
				}
			}
		}
	}
	return ans;
}

• 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