Submission #197741

#	Time	Username	Problem	Language	Result	Execution time	Memory
197741		Minnakhmetov	Rectangles (IOI19_rect)	C++14	0 / 100	2 ms	504 KiB

rect

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

#define ll long long

const int N = 2505;
int dx[4] = {-1, 1, 0, 0},
	dy[4] = {0, 0, -1, 1};
bool used[N][N];
int mn_x, mx_x, mn_y, mx_y, ct, n, m;

void dfs(vector<vector<int>> &a, int x, int y) {
	used[x][y] = 1;
	ct++;

	mn_x = min(mn_x, x);
	mx_x = max(mx_x, x);
	mn_y = min(mn_y, y);
	mx_y = max(mx_y, y);

	for (int i = 0; i < 4; i++) {
		int p = x + dx[i],
			q = y + dy[i];
		if (p >= 0 && p < n && q >= 0 && q < m && 
			a[p][q] == 0 && !used[p][q]) {
			dfs(a, p, q);
		}
	}
}

ll solve01(vector<vector<int>> a) {
	n = a.size(),
		m = a[0].size();

	ll ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!used[i][j] && a[i][j] == 0) {
				mn_x = N, mx_x = -1, mn_y = N, mx_y = -1, ct = 0;
				dfs(a, i, j);
				if (ct == (mx_x - mn_x + 1) * (mx_y - mn_y + 1))
					ans++;
			}
		}
	}

	return ans;
}

ll count_rectangles(vector<vector<int>> a) {
	return solve01(a);
}

• 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