Submission #445001

#	Time	Username	Problem	Language	Result	Execution time	Memory
445001		dutch	Furniture (JOI20_furniture)	C++17	0 / 100	3 ms	716 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define invalid(i, j) min(x, y) < 0 || !min(n-x, m-y)

const int LIM = 1000;

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

int n, m, c[2*LIM];
bool g[LIM][LIM], v[LIM][LIM], inPath[LIM][LIM];

void dfs(int x, int y){
	if(invalid(x, y) || v[x][y] || g[x][y]){
		return;
	}else v[x][y] = 1;

	for(int k=0; k<2; ++k){
		dfs(x + dx[k], y + dy[k]);
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=0; i<n; ++i)
		for(int j=0; j<m; ++j)
			cin >> g[i][j];

	dfs(n-1, m-1);

	for(int i=0; i<n; ++i)
		for(int j=0; j<m; ++j)
			inPath[i][j] = v[i][j], v[i][j] = 0;

	dx[0] = dy[1] = 1;
	dfs(0, 0);

	for(int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			if(!v[i][j]) inPath[i][j] = 0;
			c[i+j] += inPath[i][j];
			v[i][j] = 0;
		}
	}

	queue<pair<int, int>> q;

	int z, a, b; cin >> z;
	while(z--){
		cin >> a >> b; --a, --b;
		if(!inPath[a][b]){
			g[a][b] = 1;
		}else if(c[a+b] > 1){
			vector<pair<int, int>> bad;

			q.emplace(a, b);
			v[a][b] = 1;
			while(!q.empty()){
				auto [x, y] = q.front(); q.pop();
				bad.emplace_back(x, y);
				for(int k=0; k<2; ++k){
					int i = x + dx[k], j = y + dy[k];
					if(invalid(i, j) || v[i][j]) continue;
					int s = i - dx[!k], t = j - dy[!k];
					if(invalid(s, t) || g[s][t] || !inPath[s][t]){
						q.emplace(i, j);
						v[i][j] = 1;
					}
				}
			}
			for(auto &[i, j] : bad){
				inPath[i][j] = 0;
				--c[i+j];
				v[i][j] = 0;
			}
			g[a][b] = 1;
		}
		cout << g[a][b] << '\n';
 	}
}

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