oj.uz

Submission #501647

# Submission time Handle Problem Language Result Execution time Memory
501647 2022-01-04T09:11:50 Z amunduzbaev Furniture (JOI20_furniture) C++14
0 / 100
 2 ms 1164 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];

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

	int ch[6][2] = {
		{0, 1},
		{-1, 0},
		{-1, 1},
		{0, -1},
		{1, 0},
		{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();
			for(int t=0;t<6;t+=3){
				int i = u[0] + ch[t][0], j = u[1] + ch[t][1];
				int x = u[0] + ch[t+2][0], y = u[1] + ch[t+2][1];
				if(check(i, j) && !used[i][j] && (!check(x, y) || used[x][y])){
					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] && (!check(x, y) || used[x][y])){
					used[i][j] = 1;
					qq.push({i, j});
				}
			}
		}
	};
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]) check(i, j);
		}
	}
	
	vector<int> cnt(n + m + 1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(used[i][j]) continue;
			cnt[i+j]++;
		}
	}
	
	int q; cin>>q;
	while(q--){
		int i, j; cin>>i>>j;
		if(used[i][j]){
			cout<<1<<"\n";
			continue;
		}
		
		if(cnt[i + j] == 1){
			cout<<0<<"\n";
			continue;
		}
		cnt[i + j]--;
		check(i, j);
		cout<<1<<"\n";
	}
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 964 KB Output is correct
2 Incorrect 2 ms 1164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 964 KB Output is correct
2 Incorrect 2 ms 1164 KB Output isn't correct
3 Halted 0 ms 0 KB -