#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 1e3+5;
int n,m;
int A[N][N];
set<int>in[N*N],out[N*N];
int fix[N*N];
int x,a,b;
int H[N*N],cnt[N*N],can[N*N];
void erase_vertex(int x){
//cout << x << " ----" << endl;
for(auto to : out[x]){
in[to].erase(x);//cout << x << " " << to << endl;
}
for(auto to : in[x]){
out[to].erase(x); //cout << to << " " << x << endl;
}
//cout << "----" << endl;
}
void add_edge(int x,int y){
out[x].insert(y); in[y].insert(x);
out[x].insert(y); in[y].insert(x);
}
void dfs(int x,int h){
//cout << x << endl;
fix[x] = 1;
H[x] = h;
if(x == n*m){
can[x] = 1;
cnt[h]++;
return ;
}
for(auto to : out[x]){
if(fix[to] == 0)
dfs(to,h+1);
can[x] |= can[to];
}
cnt[h] += can[x];
}
bool check(int x){
if(cnt[H[x]+1] > out[x].size()) return true;
for(auto to : out[x]){
if(in[to].size() == 2) return true;
}
return false;
}
void go_down(int x,int p){
in[x].erase(p);
if(in[x].size() == 1) return ;
cnt[H[x]]--;
can[x] = 0;
for(auto to : out[x]){
go_down(to,x);
}
}
void go_up(int x,int p){
out[x].erase(p);
if(out[x].size() == 1) return ;
cnt[H[x]]--;
can[x] = 0;
for(auto to : in[x]){
go_up(to,x);
}
}
int main(){
cin >> n >> m;
int a = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> A[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a++;
if(!A[i][j] && !A[i][j+1] && j+1 <= m)add_edge(a,a+1);
if(!A[i][j] && !A[i+1][j] && i+1 <= n)add_edge(a,a+m);
}
}
//cout << 1 << endl;
dfs(1,0);
for(int i = 1; i <= n*m; i++) if(can[i] == 0) erase_vertex(i);
int q;
cin >> q;
while(q--){
cin >> a >> b;
x = (a-1)*m+b;
if(can[x] == 0){
cout << 1 << endl;
continue;
}
if(check(x)){
cout << 1 << endl;
can[x] = 0; cnt[H[x]]--;
for(auto to : out[x])go_down(to,x);
for(auto to : in[x])go_up(to,x);
} else {
cout << 0 << endl;
}
}
}
Compilation message
furniture.cpp: In function 'bool check(int)':
furniture.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if(cnt[H[x]+1] > out[x].size()) return true;
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
96620 KB |
Output is correct |
2 |
Correct |
71 ms |
96236 KB |
Output is correct |
3 |
Correct |
75 ms |
97004 KB |
Output is correct |
4 |
Correct |
92 ms |
97132 KB |
Output is correct |
5 |
Correct |
90 ms |
97260 KB |
Output is correct |
6 |
Correct |
94 ms |
97772 KB |
Output is correct |
7 |
Correct |
93 ms |
97772 KB |
Output is correct |
8 |
Correct |
94 ms |
97772 KB |
Output is correct |
9 |
Correct |
96 ms |
97900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
96620 KB |
Output is correct |
2 |
Correct |
71 ms |
96236 KB |
Output is correct |
3 |
Correct |
75 ms |
97004 KB |
Output is correct |
4 |
Correct |
92 ms |
97132 KB |
Output is correct |
5 |
Correct |
90 ms |
97260 KB |
Output is correct |
6 |
Correct |
94 ms |
97772 KB |
Output is correct |
7 |
Correct |
93 ms |
97772 KB |
Output is correct |
8 |
Correct |
94 ms |
97772 KB |
Output is correct |
9 |
Correct |
96 ms |
97900 KB |
Output is correct |
10 |
Correct |
160 ms |
104684 KB |
Output is correct |
11 |
Correct |
82 ms |
97260 KB |
Output is correct |
12 |
Correct |
1776 ms |
271468 KB |
Output is correct |
13 |
Correct |
606 ms |
236376 KB |
Output is correct |
14 |
Correct |
3178 ms |
267300 KB |
Output is correct |
15 |
Correct |
3460 ms |
277416 KB |
Output is correct |
16 |
Correct |
3377 ms |
292996 KB |
Output is correct |
17 |
Correct |
3683 ms |
303660 KB |
Output is correct |
18 |
Correct |
3753 ms |
298348 KB |
Output is correct |
19 |
Correct |
3725 ms |
310376 KB |
Output is correct |
20 |
Correct |
3845 ms |
310292 KB |
Output is correct |
21 |
Correct |
3829 ms |
310420 KB |
Output is correct |