Submission #501690

#	Time	Username	Problem	Language	Result	Execution time	Memory
501690		amunduzbaev	Furniture (JOI20_furniture)	C++14	100 / 100	310 ms	27716 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95