This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |