Submission #1047651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047651		MercubytheFirst	Rectangles (IOI19_rect)	C++14	0 / 100	87 ms	180268 KiB

rect

#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 = y = -1; 
		xx = yy = -37;
	}
	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
*/

• 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