제출 #1152896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152896		the_coding_pooh	Rectangles (IOI19_rect)	C++20	13 / 100	1081 ms	927016 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};

int NN, MM;

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(x + dx[d] < 0 || y + dy[d] < 0 || x + dx[d] > NN + 1 || y + dy[d] > MM + 1 || 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; i++){
		for (int j = 0; j < m; j++){
			graph[i + 1][j + 1] = (a[i][j] == 1);
		}
	}
	graph[0][0] = 1;
	int ret = 0;
	NN = n;
	MM = m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if(graph[i][j])
				continue;
			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: 13 / 13
• Subtask 7: 0 / 28