Submission #445010

#	Time	Username	Problem	Language	Result	Execution time	Memory
445010		dutch	Furniture (JOI20_furniture)	C++17	100 / 100	405 ms	15044 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define invalid(e, f) (min(e, f) < 0 || !min(n-e, m-f) || g[e][f])

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];
queue<pair<int, int>> q;

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

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

void add(int a, int b){
	q.emplace(a, b);
	inPath[a][b] = 0;
	--c[a+b];
	v[a][b] = 1;
}

void remove(int a, int b){
	add(a, b);
	while(!q.empty()){
		auto [x, y] = q.front(); q.pop();
		v[x][y] = 0;
		for(int k=0; k<2; ++k){
			int i = x + dx[k], j = y + dy[k];
			if(invalid(i, j) || !inPath[i][j] || v[i][j]) continue;
			int s = i - dx[!k], t = j - dy[!k];
			if(invalid(s, t) || !inPath[s][t]){
				add(i, j);
			}
		}
	}
}

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;
		}
	}


	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){
			remove(a, b);
			++c[a+b];
			inPath[a][b] = 1;
			dx[0] = dy[1] = -1;
			remove(a, b);
			dx[0] = dy[1] = 1;
			g[a][b] = 1;
		}
		cout << g[a][b] << '\n';
 	}
}

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