제출 #1290746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290746		enzy	Rectangles (IOI19_rect)	C++20	13 / 100	511 ms	497572 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, pd[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);
	if(ma_lin[c]==n||me_lin[c]==1) pd[c]=0;
	if(ma_col[c]==m||me_col[c]==1) pd[c]=0;
	//cout << x << ' ' << y << " " << pd[c] << endl;
	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]){
				pd[++c]++;
				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]&&pd[i]) 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: 13 / 13
• Subtask 7: 0 / 28