Submission #292911

#	Time	Username	Problem	Language	Result	Execution time	Memory
292911		arnold518	Furniture (JOI20_furniture)	C++14	100 / 100	936 ms	38068 KiB

furniture

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;

int N, M, Q, A[MAXN+10][MAXN+10];
int dp1[MAXN+10][MAXN+10], dp2[MAXN+10][MAXN+10];
int S[MAXN+10][MAXN+10], C[MAXN+10];

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d", &A[i][j]);

	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
	{
		if(i==1 && j==1) dp1[i][j]=1;
		else if(A[i][j]) dp1[i][j]=0;
		else dp1[i][j]=dp1[i-1][j]|dp1[i][j-1];
	}

	for(int i=N; i>=1; i--) for(int j=M; j>=1; j--)
	{
		if(i==N && j==M) dp2[i][j]=1;
		else if(A[i][j]) dp2[i][j]=0;
		else dp2[i][j]=dp2[i+1][j]|dp2[i][j+1];
	}

	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
	{
		if(A[i][j]==0 && dp1[i][j]==1) S[i+j][i]++;
		if(A[i][j]==0 && dp2[i][j]==1) S[i+j][i]++;
		if(S[i+j][i]==2) C[i+j]++;
	}

	scanf("%d", &Q);
	for(int p=1; p<=Q; p++)
	{
		int y, x;
		scanf("%d%d", &y, &x);
			
		bool flag;
		if(dp1[y][x]==0 || dp2[y][x]==0) flag=true;
		else
		{
			if(C[y+x]>=2) flag=true;
			else flag=false;
		}

		printf("%d\n", flag);
		if(!flag) continue;

		queue<pii> Q;
		if(dp1[y][x])
		{	
			Q.push({y, x}); dp1[y][x]=0;
			while(!Q.empty())
			{
				pii now=Q.front(); Q.pop();
				int y=now.first, x=now.second;
				if(S[y+x][y]==2) C[y+x]--;
				S[y+x][y]--;

				if(dp1[y+1][x] && !dp1[y+1][x-1])
				{
					dp1[y+1][x]=0;
					Q.push({y+1, x});
				}
				if(dp1[y][x+1] && !dp1[y-1][x+1])
				{
					dp1[y][x+1]=0;
					Q.push({y, x+1});
				}
			}
		}

		if(dp2[y][x])
		{
			Q.push({y, x}); dp2[y][x]=0;
			while(!Q.empty())
			{
				pii now=Q.front(); Q.pop();
				int y=now.first, x=now.second;
				if(S[y+x][y]==2) C[y+x]--;
				S[y+x][y]--;

				if(dp2[y-1][x] && !dp2[y-1][x+1])
				{
					dp2[y-1][x]=0;
					Q.push({y-1, x});
				}
				if(dp2[y][x-1] && !dp2[y+1][x-1])
				{
					dp2[y][x-1]=0;
					Q.push({y, x-1});
				}
			}
		}
	}
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:17:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d", &A[i][j]);
      |                                                  ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
furniture.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |   scanf("%d%d", &y, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95