Submission #1255522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255522		Seyyed_Mojtaba_Mortazavi	Furniture (JOI20_furniture)	C++20	100 / 100	1237 ms	8388 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

const int MAXN = 1e3 + 10;

int c[MAXN][MAXN];
int cnt[MAXN << 1];
bool mark1[MAXN][MAXN];
bool mark2[MAXN][MAXN];

void BFS1(int x, int y)
{
	if (mark1[x][y] && mark2[x][y])
		cnt[x + y]--;
	c[x][y] = 1;
	queue <pii> q;
	if (mark1[x][y])
	{
		mark1[x][y] = false;
		q.push({x, y});
		while (!q.empty())
		{
			auto [X, Y] = q.front();
			q.pop();
			if (mark1[X - 1][Y] && !mark1[X - 1][Y + 1])
			{
				mark1[X - 1][Y] = false;
				cnt[X + Y - 1] -= mark2[X - 1][Y];
				q.push({X - 1, Y});
			}
			if (mark1[X][Y - 1] & !mark1[X + 1][Y - 1])
			{
				mark1[X][Y - 1] = false;
				cnt[X + Y - 1] -= mark2[X][Y - 1];
				q.push({X, Y - 1});
			}
		}
	}
}

void BFS2(int x, int y)
{
	if (mark1[x][y] && mark2[x][y])
		cnt[x + y]--;
	c[x][y] = 1;
	queue <pii> q;
	if (mark2[x][y])
	{
		mark2[x][y] = false;
		q.push({x, y});
		while (!q.empty())
		{
			auto [X, Y] = q.front();
			q.pop();
			if (mark2[X + 1][Y] && !mark2[X + 1][Y - 1])
			{
				mark2[X + 1][Y] = false;
				cnt[X + Y + 1] -= mark1[X + 1][Y];
				q.push({X + 1, Y});
			}
			if (mark2[X][Y + 1] & !mark2[X - 1][Y + 1])
			{
				mark2[X][Y + 1] = false;
				cnt[X + Y + 1] -= mark1[X][Y + 1];
				q.push({X, Y + 1});
			}
		}
	}
}

signed main()
{
	int n, m, q;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		c[i][0] = c[i][m + 1] = 1;
	for (int i = 1; i <= m; i++)
		c[0][i] = c[n + 1][i] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cnt[i + j]++;
			mark1[i][j] = mark2[i][j] = true;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> c[i][j];
			if (c[i][j])
			{
				BFS1(i, j);
				BFS2(i, j);
			}
		}
	}
	cin >> q;
	while (q--)
	{
		int x, y;
		cin >> x >> y;
		if (cnt[x + y] >= 2 || !mark1[x][y] || !mark2[x][y])
		{
			BFS1(x, y);
			BFS2(x, y);
			cout << 1 << endl;
		}
		else
		{
			cout << 0 << endl;
		}
	}
	return 0;
}

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