Submission #598099

#	Time	Username	Problem	Language	Result	Execution time	Memory
598099		yutabi	Rectangles (IOI19_rect)	C++14	13 / 100	397 ms	408904 KiB

rect

#include "rect.h"


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


int N;
int M;


int L;
int R;
int U;
int D;

int k;

vector <vector <bool> > V;


void DFS(int y, int x)
{
	k++;

	V[y][x]=1;

	L=min(x,L);
	R=max(R,x);
	U=min(U,y);
	D=max(D,y);

	if(y>0 && V[y-1][x]==0)
	{
		DFS(y-1,x);
	}

	if(x>0 && V[y][x-1]==0)
	{
		DFS(y,x-1);
	}

	if(y<N-1 && V[y+1][x]==0)
	{
		DFS(y+1,x);
	}

	if(x<M-1 && V[y][x+1]==0)
	{
		DFS(y,x+1);
	}
}



long long count_rectangles(std::vector<std::vector<int> > a)
{
	vector <vector <bool> > v(a.size(),vector <bool> (a[0].size(),0));

	int ans;

	for(int i=0;i<a.size();i++)
	{
		for(int j=0;j<a[i].size();j++)
		{
			if(a[i][j]>0)
			{
				v[i][j]=1;
			}
		}
	}

	N=a.size();
	M=a[0].size();

	V=v;

	for(int i=0;i<a.size();i++)
	{
		for(int j=0;j<a[i].size();j++)
		{
			if(V[i][j]==0)
			{
				L=R=j;
				U=D=i;

				k=0;

				DFS(i,j);

				//printf("aaa");

				if(L>0 && U>0 && R<M-1 && D<N-1 && (D-U+1)*(R-L+1)==k)
				{
					ans++;
				}
			}
		}
	}





	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<a.size();i++)
      |              ~^~~~~~~~~
rect.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j=0;j<a[i].size();j++)
      |               ~^~~~~~~~~~~~
rect.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=0;i<a.size();i++)
      |              ~^~~~~~~~~
rect.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int j=0;j<a[i].size();j++)
      |               ~^~~~~~~~~~~~
rect.cpp:105:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |  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