oj.uz

Submission #445010

# Submission time Handle Problem Language Result Execution time Memory
445010 2021-07-16T08:35:44 Z dutch Furniture (JOI20_furniture) C++17
100 / 100
 405 ms 15044 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 4 ms 720 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 4 ms 720 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 13 ms 716 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 220 ms 7824 KB Output is correct
13 Correct 99 ms 4968 KB Output is correct
14 Correct 359 ms 12716 KB Output is correct
15 Correct 371 ms 12960 KB Output is correct
16 Correct 384 ms 13764 KB Output is correct
17 Correct 400 ms 14532 KB Output is correct
18 Correct 396 ms 14180 KB Output is correct
19 Correct 405 ms 14800 KB Output is correct
20 Correct 397 ms 15044 KB Output is correct
21 Correct 400 ms 14916 KB Output is correct