제출 #583826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583826		joelau	Rectangles (IOI19_rect)	C++14	13 / 100	531 ms	392540 KiB

rect

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

long long N,M,ufds[6500005],rnk[6500005],X1[6500005],X2[6500005],Y1[6500005],Y2[6500005], sz[6500005], dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};

long long findSet(long long i) {
	return ufds[i] == i ? i : ufds[i] = findSet(ufds[i]);
}

void unionSet(long long i, long long j) {
	long long a = findSet(i), b = findSet(j);
	if (a == b) return;
	if (rnk[a] < rnk[b])
		X1[b] = min(X1[a],X1[b]), X2[b] = max(X2[a],X2[b]), Y1[b] = min(Y1[a],Y1[b]), Y2[b] = max(Y2[a],Y2[b]), sz[b] += sz[a], ufds[a] = b;
	if (rnk[a] > rnk[b]) 
		X1[a] = min(X1[a],X1[b]), X2[a] = max(X2[a],X2[b]), Y1[a] = min(Y1[a],Y1[b]), Y2[a] = max(Y2[a],Y2[b]), sz[a] += sz[b], ufds[b] = a;
	if (rnk[a] == rnk[b]) 
		X1[b] = min(X1[a],X1[b]), X2[b] = max(X2[a],X2[b]), Y1[b] = min(Y1[a],Y1[b]), Y2[b] = max(Y2[a],Y2[b]), sz[b] += sz[a], ufds[a] = b, rnk[b]++;
}

long long count_rectangles(vector<vector<int> > a) {
	N = a.size(), M = a[0].size();
	for (long long i = 0; i < N; ++i) for (long long j = 0; j < M; ++j) 
		ufds[i*M+j] = i*M+j, rnk[i*M+j] = 1, X1[i*M+j] = X2[i*M+j] = i, Y1[i*M+j] = Y2[i*M+j] = j, sz[i*M+j] = 1;
	for (long long i = 0; i < N; ++i) for (long long j = 0; j < M; ++j) if (a[i][j] == 0) {
		for (long long k = 0; k < 4; ++k) {
			long long nx = i + dx[k], ny = j + dy[k];
			if (nx >= 0 && nx < N && ny >= 0 && ny < M && a[nx][ny] == 0) unionSet(i*M+j,nx*M+ny);
		}
	}
	long long ans = 0;
	for (long long i = 1; i < N-1; ++i) for (long long j = 1; j < M-1; ++j)
		if (findSet(i*M+j) == i*M+j && a[i][j] == 0 && X1[i*M+j] != 0 && X2[i*M+j] != N-1 && Y1[i*M+j] != 0 && Y2[i*M+j] != M-1 && sz[i*M+j] == (X2[i*M+j]-X1[i*M+j]+1) * (Y2[i*M+j]-Y1[i*M+j]+1)) ans++;
	return ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28