제출 #1290741

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290741		enzy	Rectangles (IOI19_rect)	C++20	0 / 100	123 ms	99752 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2502;
int v[maxn][maxn], marc[maxn][maxn], ma_col[maxn*maxn], me_col[maxn*maxn], qtd[maxn*maxn], ma_lin[maxn*maxn], me_lin[maxn*maxn], n, m, ma[maxn*maxn], me[maxn*maxn];
int dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
bool in(int x, int y){
	return 1<=x&&x<=n&&1<=y&&y<=m;
}
void dfs(int x, int y, int c){
	qtd[c]++;
	marc[x][y]=c;
	ma_col[c]=max(ma_col[c],y); me_col[c]=min(me_col[c],y);
	ma_lin[c]=max(ma_lin[c],x); me_lin[c]=min(me_lin[c],x);
	ma[c]=max(ma_col[c],ma_lin[c]); me[c]=min(me_col[c],me_lin[c]);
	for(int i=0;i<4;i++){
		int nx=x+dx[i], ny=y+dy[i];
		if(in(nx,ny)&&v[nx][ny]&&marc[nx][ny]==0) dfs(nx,ny,c);
	}
}
ll count_rectangles(vector<vector<int> > a){
	n=a.size(), m=a[0].size();
	memset(me_col,1,sizeof(me_col)); memset(me_lin,1,sizeof(me_lin));
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			v[i+1][j+1]=a[i][j]^1;
	int c=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) if(marc[i][j]==0&&v[i][j]) dfs(i,j,++c);
	ll resp=0;
	for(int i=1;i<=c;i++) if((ma_col[i]-me_col[i]+1)*(ma_lin[i]-me_lin[i]+1)==qtd[i]&&ma[i]!=n&&me[i]!=1) resp++;
	return resp;
}

• 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