oj.uz

Submission #1047643

# Submission time Handle Problem Language Result Execution time Memory
1047643 2024-08-07T14:36:04 Z MercubytheFirst Rectangles (IOI19_rect) C++14
0 / 100
 1 ms 860 KB 
#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);
		// 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();
	const ll dx[] = {0, +1, 0, -1},
						dy[] = {+1, 0, -1, 0};
	vector<vector<bool> > in_dsu(n, vector<bool>(m));
	DSU dsu;
	for(ll i = 1; i + 1 < n; ++i) {
		for(ll j = 1; j + 1 < 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(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 0 0 0 1
1 0 0 0 1
1 1 1 1 1

*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -