Submission #767717

#	Time	Username	Problem	Language	Result	Execution time	Memory
767717		ono_de206	Rectangles (IOI19_rect)	C++14	13 / 100	611 ms	227664 KiB

rect

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 2510;
int par[mxn * mxn], cnt[mxn * mxn], n, m;
pair<pair<int, int>, pair<int, int>> dp[mxn * mxn];
bool is[mxn][mxn];

void mnn(int &a, int b) {
	if(a > b) a = b;
}

void mxx(int &a, int b) {
	if(a < b) a = b;
}

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int toInt(pair<int, int> a) {
	return (a.ff - 1) * n + a.ss;
}

int get(int x) {
	if(par[x] == x) return x;
	return par[x] = get(par[x]);
}

void unite(int x, int y) {
	x = get(x), y = get(y);
	if(x == y) return;
	if(cnt[x] < cnt[y]) swap(x, y);
	par[y] = x;
	cnt[x] += cnt[y];
	mxx(dp[x].ss.ff, dp[y].ss.ff);
	mxx(dp[x].ss.ss, dp[y].ss.ss);
	mnn(dp[x].ff.ff, dp[y].ff.ff);
	mnn(dp[x].ff.ss, dp[y].ff.ss);
}

long long count_rectangles(vector<vector<int>> A) {
	n = A.size(), m = A[0].size();
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(A[i][j] == 0) {
				dp[i * m + j] = {{i, j}, {i, j}};
				par[i * m + j] = i * m + j;
				cnt[i * m + j] = 1; 
			}
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(A[i][j]) continue;
			for(int k = 0; k < 4; k++) {
				int ii = i + dx[k], jj = j + dy[k];
				if(ii >= 0 && ii < n && jj >= 0 && jj < m && A[ii][jj] == 0) {
					unite(i * m + j, ii * m + jj);
				}
			}
		}
	}
	long long ret = 0;
	set<int> s;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(A[i][j] == 1) continue;
			int id = get(i * m + j);
			if(s.find(id) != s.end()) continue;
			s.in(id);
			if((dp[id].ss.ff - dp[id].ff.ff + 1) * (dp[id].ss.ss - dp[id].ff.ss + 1) == cnt[id] && 
				dp[id].ff.ff > 0 && dp[id].ff.ss > 0 && dp[id].ss.ff < n - 1 && dp[id].ss.ss < m - 1) ret++;
		}
	}
	return ret;
}

• 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