Submission #240867

#	Time	Username	Problem	Language	Result	Execution time	Memory
240867		zoomswk	Rectangles (IOI19_rect)	C++17	13 / 100	729 ms	529912 KiB

rect

#include "rect.h"
using namespace std;

vector<vector<int>> v;

int n, m;

bool vs[2505][2505];
int cnt[2505][2505];
int minX[2505][2505];
int minY[2505][2505];
int maxX[2505][2505];
int maxY[2505][2505];

void dfs(int x, int y, int px, int py){
	if(x < 0 || y < 0 || x >= n || y >= m) return;
	if(v[x][y] == 1) return;
	if(vs[x][y]) return;
	vs[x][y] = true;
	cnt[px][py]++;
	minX[px][py] = min(minX[px][py], x);
	maxX[px][py] = max(maxX[px][py], x);
	minY[px][py] = min(minY[px][py], y);
	maxY[px][py] = max(maxY[px][py], y);
	dfs(x-1, y, px, py);
	dfs(x, y-1, px, py);
	dfs(x+1, y, px, py);
	dfs(x, y+1, px, py);
	return;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	v = a;
	n = (int)a.size();
	m = (int)a[0].size();
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			if(vs[i][j]) continue;
			minX[i][j] = 1e9;
			maxX[i][j] = -1;
			minY[i][j] = 1e9;
			maxY[i][j] = -1;
			dfs(i, j, i, j);
		}
	}
	long long res = 0;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			if(cnt[i][j] == 0) continue;
			if((maxX[i][j]-minX[i][j]+1)*(maxY[i][j]-minY[i][j]+1) != cnt[i][j]) continue;
			if(minX[i][j] == 0 || maxX[i][j] == n-1 || minY[i][j] == 0 || maxY[i][j] == m-1) continue;
			res++;
		}
	}
	return res;
}

• 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