제출 #1152893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152893		the_coding_pooh	Rectangles (IOI19_rect)	C++20	0 / 100	1 ms	1604 KiB

rect

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

#define uwu return

using namespace std;

const int MAX_N = 2.5e3 + 5;

bitset <MAX_N> graph[MAX_N];

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

vector <int> dfs(int x, int y){
	graph[x][y] = 1;
	vector<int> ret = {x, x, y, y, 1};
	for (int d = 0; d < 4; d++){
		if(graph[x + dx[d]][y + dy[d]])
			continue;
		vector<int> tmp = dfs(x + dx[d], y + dy[d]);
		ret[0] = min(ret[0], tmp[0]);
		ret[2] = min(ret[2], tmp[2]);
		ret[1] = max(ret[1], tmp[1]);
		ret[3] = max(ret[3], tmp[3]);
		ret[4] += tmp[4];
	}
	return ret;
}

long long count_rectangles(vector<vector<int> > a) {
	int n = a.size(), m = a[0].size();
	for (int i = 0; i <= n + 1; i++){
		for (int j = 0; j <= m + 1; j++){
			graph[i][j] = 1;
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			graph[i + 1][j + 1] = (a[i][j] == 1);
		}
	}
	int ret = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			vector <int> tmp = dfs(i, j);
			ret += (tmp[1] - tmp[0] + 1) * (tmp[3] - tmp[2] + 1) == tmp[4];
		}
	}
	uwu 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