#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using ll = long long;
ll n, m;
struct Node
{
ll sz, par, v, x, xx, y, yy;
Node() { sz = par = v = x = xx = y = yy = -1; }
Node(ll i, ll j) {
v = m*i + j;
par = v;
sz = 1;
x = xx = i;
y = yy = j;
}
bool is_rect(void) {
assert(par == v);
assert(xx >= x and yy >= y);
if(x <= 0 or y <= 0 or xx >= n - 1 or yy >= n - 1) {
return false;
}
// cout <<
return (xx - x + 1) * (yy - y + 1) == sz;
}
};
struct DSU
{
vector<Node> dsu;
DSU() {
dsu.resize(n*m);
}
ll find(ll x) {
if(dsu[x].par == x) {
return x;
}
return dsu[x].par = find(dsu[x].par);
}
bool merge(ll x, ll y) {
x = find(x);
y = find(y);
if(x == y) {
return false;
}
if(dsu[x].sz < dsu[y].sz) {
swap(x, y);
}
dsu[x].sz += dsu[y].sz;
dsu[y].par = x;
dsu[x].x = min(dsu[x].x, dsu[y].x);
dsu[x].xx = max(dsu[x].xx, dsu[y].xx);
dsu[x].y = min(dsu[x].y, dsu[y].y);
dsu[x].yy = max(dsu[x].yy, dsu[y].yy);
return true;
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
if(n <= 2 or m <= 2) {
return 0;
}
const ll dx[] = {0, +1, 0, -1},
dy[] = {+1, 0, -1, 0};
vector<vector<bool> > in_dsu(n, vector<bool>(m));
DSU dsu;
auto ok = [=](int x, int y) -> bool
{
return 0 <= x and x < n and 0 <= y and y < m;
};
for(ll i = 0; i < n; ++i) {
for(ll j = 0; j < m; ++j) {
if(a[i][j] == 1) {
continue;
}
in_dsu[i][j] = true;
dsu.dsu[m*i + j] = Node(i, j);
for(ll d = 0; d < 4; ++d) {
ll ii = i + dx[d], jj = j + dy[d];
if(!ok(ii, jj)) {
continue;
}
if(in_dsu[ii][jj]) {
dsu.merge(m*i + j, m*ii + jj);
}
}
}
}
ll ans = 0;
for(ll i = 0; i< n; ++i) {
for(ll j = 0; j < m; ++j) {
const ll vn = m*i + j;
if(!in_dsu[i][j] or dsu.dsu[vn].par != vn) {
continue;
}
// cout << "hi : " << i << ' ' << j << ' ' << dsu.dsu[vn].sz << ' ' << dsu.dsu[vn].y << ' ' << dsu.dsu[vn].yy << (dsu.dsu[vn].is_rect() ? " Yep " : " Nope ") << endl;
// cout << in_dsu[i][j] << ' ';
ans += dsu.dsu[vn].is_rect();
}
// cout << endl;
}
return ans;
}
/*
5 5
1 1 1 1 1
1 0 0 0 1
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
88 ms |
180128 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
