Submission #145997

#	Time	Username	Problem	Language	Result	Execution time	Memory
145997		Mamnoon_Siam	Rectangles (IOI19_rect)	C++17	13 / 100	693 ms	285824 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e5;
const int maxn = 2503;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, -1, 0, +1};

int n, m;
int a[maxn][maxn];
int vis[maxn][maxn];

int cnt = 0;
int mnx, mxx, mny, mxy;
void dfs(int x, int y) {
	cnt++;

	vis[x][y] = 1;

	mnx = min(mnx, x);
	mxx = max(mxx, x);
	mny = min(mny, y);
	mxy = max(mxy, y);

	for(int i = 0; i < 4; i++) {
		int xx = dx[i] + x;
		int yy = dy[i] + y;
		if(1 <= xx and xx <= n and 1 <= yy and yy <= m and a[xx][yy] == 0 and !vis[xx][yy]) {
			dfs(xx, yy);
		}
	}
}

long long count_rectangles(vector<vector<int> > aa) {
	n = aa.size(), m = aa[0].size();
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			a[i + 1][j + 1] = aa[i][j];
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(!vis[i][j] and a[i][j] == 0) {
				mnx = inf, mxx = -inf;
				mny = inf, mxy = -inf;
				cnt = 0;
				dfs(i, j);
				if((mxx - mnx + 1) * (mxy - mny + 1) == cnt and mnx != 1 and mxx != n and mny != 1 and mxy != m) {
					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