Submission #1290790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290790		julia_08	Rectangles (IOI19_rect)	C++20	0 / 100	64 ms	45720 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using ll = long long;

using namespace std;

const int MAXN = 2510;

int mat[MAXN][MAXN];

int marc[MAXN][MAXN];

int n, m;

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

bool check(int x, int y){
	return 1 < x && x < n && 1 < y && y < m && mat[x][y] == 0;
}

int min_x, min_y, max_x, max_y, cur = 0;

vector<pair<int, int>> comp;

void dfs(int x, int y){

	marc[x][y] = cur;

	comp.push_back({x, y});

	min_x = min(min_x, x);
	min_y = min(min_y, y);

	max_x = max(max_x, x);
	max_y = max(max_y, y);

	for(int k=0; k<4; k++){
		int nx = x + dx[k], ny = y + dy[k];
		if(!marc[nx][ny] && check(nx, ny)) dfs(nx, ny);
	}

}

ll count_rectangles(vector<vector<int>> a){

	n = (int) a.size();

	m = (int) a[0].size();

	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			mat[i + 1][j + 1] = a[i][j];
		}
	}

	dfs(1, 1);

	ll ans = 0;

	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){

			if(marc[i][j] || mat[i][j] == 1) continue;

			min_x = min_y = 1e9;
			max_x = max_y = 0;

			cur ++;

			comp.clear();

			dfs(i, j);

			if((max_x - min_x + 1) * (max_y - min_y + 1) == (int) comp.size()){

				// eh um retangulo
				// checo se todas as bordas sao 1

				bool ok = true;

				for(auto [x, y] : comp){

					for(int k=0; k<4; k++){
						int nx = x + dx[k], ny = y + dy[k];
						if(marc[nx][ny] == cur || mat[nx][ny] == 1) continue;
						ok = false;
					}

				}

				if(ok) 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: 0 / 13
• Subtask 7: 0 / 28