oj.uz

Submission #501690

# Submission time Handle Problem Language Result Execution time Memory
501690 2022-01-04T10:14:37 Z amunduzbaev Furniture (JOI20_furniture) C++14
100 / 100
 310 ms 27716 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 1e3 + 5;
int a[N][N], used[N][N], cnt[N + N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int n, m; cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			cnt[i + j]++;
		}
	}
	
	int ch[6][2] = {
		{0, 1},
		{-1, 0},
		{-1, 1},
		{1, 0},
		{0, -1},
		{1, -1}
	};

	auto check = [&](int i, int j){
		queue<ar<int, 2>> qq;
		used[i][j] = 1;
		qq.push({i, j});
		
		auto check = [&](int i, int j) { return (1 <= i && i <= n && 1 <= j && j <= m); };
		while(!qq.empty()){
			auto u = qq.front(); qq.pop();
			cnt[u[0] + u[1]]--;
 			for(int t=0;t<6;t+=3){
				int x = u[0] + ch[t+2][0], y = u[1] + ch[t+2][1];
				if(!check(x, y) || used[x][y]){
					int i = u[0] + ch[t][0], j = u[1] + ch[t][1];
					if(check(i, j) && !used[i][j]){
						used[i][j] = 1, qq.push({i, j});
					} i = u[0] + ch[t+1][0], j = u[1] + ch[t+1][1];
					if(check(i, j) && !used[i][j]){
						used[i][j] = 1, qq.push({i, j});
					}
				}
			}
		}
	};
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!used[i][j] && a[i][j]) check(i, j);
		}
	}
	
	int q; cin>>q;
	while(q--){

	//~ for(int i=1;i<=n;i++){
		//~ for(int j=1;j<=m;j++){
			//~ cout<<used[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";

		int i, j; cin>>i>>j;
		if(used[i][j]){
			cout<<1<<"\n";
			continue;
		}
		
		if(cnt[i + j] == 1){
			cout<<0<<"\n";
			continue;
		}
		
		check(i, j);
		cout<<1<<"\n";
	}

	//~ for(int i=1;i<=n;i++){
		//~ for(int j=1;j<=m;j++){
			//~ cout<<used[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
}

/*

5
5
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0

9
1 5
5 1
3 3
1 2
2 2
4 3
4 5
1 4
3 2

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 3 ms 1360 KB Output is correct
7 Correct 3 ms 1360 KB Output is correct
8 Correct 5 ms 1356 KB Output is correct
9 Correct 6 ms 1356 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 3 ms 1360 KB Output is correct
7 Correct 3 ms 1360 KB Output is correct
8 Correct 5 ms 1356 KB Output is correct
9 Correct 6 ms 1356 KB Output is correct
10 Correct 11 ms 1540 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 159 ms 20444 KB Output is correct
13 Correct 65 ms 17084 KB Output is correct
14 Correct 247 ms 24424 KB Output is correct
15 Correct 267 ms 24664 KB Output is correct
16 Correct 277 ms 25812 KB Output is correct
17 Correct 294 ms 27268 KB Output is correct
18 Correct 260 ms 26316 KB Output is correct
19 Correct 310 ms 27708 KB Output is correct
20 Correct 260 ms 27672 KB Output is correct
21 Correct 294 ms 27716 KB Output is correct