Submission #962223

#	Time	Username	Problem	Language	Result	Execution time	Memory
962223		0npata	Furniture (JOI20_furniture)	C++17	100 / 100	1918 ms	114024 KiB

furniture

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

#define vec vector
#define pb push_back
#define pi pair<int, int>
#define fst first
#define snd second



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vec<vec<int>> g(n, vec<int>(m));

	for(int i = 0; i<n; i++) {
		for(int j = 0; j<m; j++) {
			cin >> g[i][j];
		}
	}



	set<pi> fc;
	set<pi> fr;

	vec<vec<bool>> vis(n, vec<bool>(m));
	vec<vec<int>> ok(n, vec<int>(m));

	vis[0][0] = true;

	for(int i = 0; i<n; i++) {
		for(int j = 0; j < m; j++) {
			if(i==0 && j == 0) continue;
			if(g[i][j]) continue;
			bool res = false;
			if(j > 0) res |= vis[i][j-1];
			if(i > 0) res |= vis[i-1][j];
			vis[i][j] = res;
		}
	}

	ok[n-1][m-1] = true;
	for(int i = n-1; i>=0; i--) {
		for(int j = m-1; j>=0; j--) {
			if(i==n-1 && j==m-1) continue;
			if(g[i][j]) continue;
			bool res = false;
			if(j < m-1) res |= ok[i][j+1];
			if(i < n-1) res |= ok[i+1][j];
			ok[i][j] = res & vis[i][j];

			if(ok[i][j]) {
				fc.insert({i, j});
				fr.insert({j, i});
			}
		}
	}




	int q;
	cin >> q;
	while(q--) {
		int r, c;
		cin >> r >> c;
		r--;c--;

		// check whether is a critical point
		int cp = true;
		auto lbcol_it = fc.lower_bound({r+1, 0});
		if(lbcol_it != fc.end()) {
			pi lbcol = *lbcol_it;
			int lbr = lbcol.fst;
			int lbc = lbcol.snd;

			if(lbr == r+1 && lbc < c) {
				cp = false;
			}
		}
		auto rtrow_it = fr.lower_bound({c+1, 0});
		if(rtrow_it != fr.end()) {
			auto rtrow = *rtrow_it;
			int rtc = rtrow.fst;
			int rtr = rtrow.snd;

			if(rtc == c+1 && rtr < r) {
				cp = false;
			}
		}

		if(cp) {
			cout << '0' << '\n';
			continue;
		}

		cout << '1' << '\n';

		auto remove = [&](pi pos) {
			vec<pi> stack{pos};
			while(stack.size() > 0) {
				pi cur = stack.back();
				stack.pop_back();

				int cr = cur.fst;
				int cc = cur.snd;

				fc.erase({cr, cc});
				fr.erase({cc, cr});

				ok[cr][cc] = false;

				// push down
				if(cr < n-1 && ok[cr+1][cc]) {
					// check whether its left is still in tact
					if(cc == 0 || !ok[cr+1][cc-1]) {
						stack.pb({cr+1, cc});
					}
				}
				// push right
				if(cc < m-1 && ok[cr][cc+1]) {
					// check whether its top is still in tact
					if(cr == 0 || !ok[cr-1][cc+1]) {
						stack.pb({cr, cc+1});
					}
				}
			}
		};

		vec<pi> stack{{r, c}};
		while(stack.size() >0) {
			pi cur = stack.back();
			stack.pop_back();
			remove(cur);

			int cr = cur.fst;
			int cc = cur.snd;

			// push up
			if(cr > 0 && ok[cr-1][cc]) {
				// check whether its right is still in tact
				if(cc == m-1 || !ok[cr-1][cc+1]) {
					stack.pb({cr-1, cc});
				}
			}
			// push left
			if(cc > 0 && ok[cr][cc-1]) {
				// check whether its down is still in tact
				if(cr == n-1 || !ok[cr+1][cc-1]) {
					stack.pb({cr, cc-1});
				}
			}
		}
	}
}

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