Submission #1047643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047643		MercubytheFirst	Rectangles (IOI19_rect)	C++14	0 / 100	1 ms	860 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 = 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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28