Submission #1302071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302071		duyanhchupapi	Furniture (JOI20_furniture)	C++20	100 / 100	370 ms	6272 KiB

furniture

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = 1002, inf = 2e9;
int n, m, q;
bool c[N][N], pf[N][N], sf[N][N], only[N][N];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0);
	// freopen(".INP", "r", stdin);
	// freopen(".OUT", "w", stdout);
	cin >> n >> m;
	for (int i=1;i<=n;++i) {
		for (int j=1;j<=m;++j) cin >> c[i][j];
	}
	
	pf[1][1] = 1;
	for (int i=1;i<=n;++i) {
		for (int j=1;j<=m;++j) {
			if (pf[i][j]) {
				if (!c[i + 1][j]) pf[i + 1][j] = 1;
				if (!c[i][j + 1]) pf[i][j + 1] = 1;
			}
		}
	} 
	
	sf[n][m] = 1;
	for (int i=n;i>=1;--i) {
		for (int j=m;j>=1;--j) {
			if (sf[i][j]) {
				if (!c[i - 1][j]) sf[i - 1][j] = 1;
				if (!c[i][j - 1]) sf[i][j - 1] = 1;
			}		
		}
	}
	
	for (int i=1;i<=n;++i) {
		for (int j=1;j<=m;++j) {
			c[i][j] = (pf[i][j] && sf[i][j]);
			//cout << c[i][j] << " ";
		} //cout << '\n';
	}
	
	cin >> q;
	while (q--) {
		int x,y;
		cin >> x >> y;
		if (!c[x][y]) cout << 1;
		else if (only[x][y]) cout << 0;
		else {
			bool del = 0;
			for (int i=1;i<y;++i) if (c[x][i] && c[x + 1][i]) del = 1;
			for (int i=1;i<x;++i) if (c[i][y] && c[i][y + 1]) del = 1;
			//cout << ":" << del << '\n';
			
			if (del) {
				queue <pair <int, int>> q;
				q.emplace(x, y);
				c[x][y] = 0;
				
				//for (int i=1;i<=n;++i) {
				//	for (int j=1;j<=m;++j) cout << c[i][j] << ' '; cout << '\n';
				//}
				
				while (!q.empty()) {
					int u = q.front().first, v = q.front().second;
					q.pop();
					
					for (int t=0;t<4;++t) {
						int nx = u + dx[t];
						int ny = v + dy[t];
						if (!c[nx][ny]) continue;
						bool c1 = (c[nx - 1][ny] || c[nx][ny - 1]);
						bool c2 = (c[nx + 1][ny] || c[nx][ny + 1]);
						if ((!c1 && (nx != 1 || ny != 1)) || (!c2 && (nx != n || ny != m))) {
							//cout << nx << ' ' << ny << '\n';
							q.emplace(nx, ny);
							c[nx][ny] = 0;
						} 
					}
				}
				
				//for (int i=1;i<=n;++i) {
				//	for (int j=1;j<=m;++j) cout << c[i][j] << ' '; cout << '\n';
				//}
			}
			else only[x][y] = 1;
			
			if (del) cout << 1;
			else cout << 0;
		}
			
		cout << '\n';
	}	
	                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
}

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