Submission #443299

#	Time	Username	Problem	Language	Result	Execution time	Memory
443299		vanic	Rectangles (IOI19_rect)	C++14	13 / 100	488 ms	442276 KiB

rect

#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <array>

using namespace std;

typedef long long ll;

const int maxn=2505, inf=1e9;

const int xp[]={0, 1, 0, -1};
const int yp[]={1, 0, -1, 0};

int n, m;
bool bio[maxn][maxn];
int v[maxn][maxn];
int maxx, maxy, minx, miny;
int br;

void dfs(int x, int y){
	int xs, ys;
	br++;
	bio[x][y]=1;
	maxx=max(maxx, x);
	maxy=max(maxy, y);
	minx=min(minx, x);
	miny=min(miny, y);
	for(int i=0; i<4; i++){
		xs=x+xp[i];
		ys=y+yp[i];
		if(xs>-1 && ys>-1 && xs<n && ys<m && !bio[xs][ys] && !v[xs][ys]){
			dfs(xs, ys);
		}
	}
}

ll count_rectangles(vector < vector < int > > a){
	n=a.size();
	m=a[0].size();
	ll sol=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			v[i][j]=a[i][j];
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(!a[i][j] && !bio[i][j]){
				maxx=0;
				maxy=0;
				minx=inf;
				miny=inf;
				br=0;
				dfs(i, j);
//				cout << minx << ' ' <<  maxx << ' ' << miny << ' ' << maxy << endl;
				if(maxx==n-1 || maxy==m-1 || minx==0 || miny==0 || br!=(maxx-minx+1)*(maxy-miny+1)){
					continue;
				}
				sol++;
			}
		}
	}
	return sol;
}

• 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