//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
//#define _int __int128
//#define int long long
int uf[2000006];
int usz[2000006];
int fin(int x){
if(uf[x]==x){return x;}
return fin(uf[x]);
}
vector<pair<int,int>>stk;
void undo(){
int pa=stk.back().first;int pb=stk.back().second;
usz[pa]-=usz[pb];
uf[pb]=pb;
stk.pop_back();
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){stk.push_back({0,0});return;}
if(usz[pb]>usz[pa]){
swap(pa,pb);
}
uf[pb]=pa;
usz[pa]+=usz[pb];
stk.push_back({pa,pb});
}
struct SGTR{
int l;int r;
vector<pair<int,int>>op;
}tr[4000006];
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
if(l==r){return;}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
}
void upd(int nw,int l,int r,pair<int,int>pr){
if(r<l){return;}
if(tr[nw].l>=l&&tr[nw].r<=r){
tr[nw].op.push_back(pr);
return;
}
if(tr[nw].l>r||tr[nw].r<l){return;}
upd(nw*2,l,r,pr);upd(nw*2+1,l,r,pr);
}
int n;
int m;
int Q;
int ain(int i,int j){
return (i-1)*m+j;
}
int bin(int i,int j){
return ain(i,j)+n*m;
}
int ogr[1010][1010];
pair<int,int>qry[1000006];
pair<int,int>q2[1000006];
int ans[1000006];
void dfs(int nw){
for(auto pr:tr[nw].op){
int x=pr.first;int y=pr.second;
mrg(x,y);
}
if(tr[nw].l==tr[nw].r){
if(fin(1)==fin(n*m)){
ans[tr[nw].l]=1;
}else{
upd(1,tr[nw].l+1,Q,q2[tr[nw].l]);
}
}else{
dfs(nw*2);dfs(nw*2+1);
}
for(auto pr:tr[nw].op){
undo();
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n*m*2;i++){
uf[i]=i;
usz[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int v;
cin>>v;
ogr[i][j]=v;
// if(v==0){mrg(ain(i,j),bin(i,j));}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i!=n){
mrg(bin(i,j),ain(i+1,j));
}
if(j!=m){
mrg(bin(i,j),ain(i,j+1));
}
}
}
cin>>Q;
buildtr(1,1,Q);
for(int i=1;i<=Q;i++){
int x;int y;
cin>>x>>y;
upd(1,1,i-1,{ain(x,y),bin(x,y)});
ogr[x][y]=-1;
q2[i]={ain(x,y),bin(x,y)};
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(ogr[i][j]==0){mrg(ain(i,j),bin(i,j));}
}
}stk.clear();
dfs(1);
for(int i=1;i<=Q;i++){
cout<<ans[i]<<"\n";
}
}
Compilation message
furniture.cpp: In function 'void dfs(int)':
furniture.cpp:83:10: warning: variable 'pr' set but not used [-Wunused-but-set-variable]
83 | for(auto pr:tr[nw].op){
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
134000 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
134004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
134000 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
134004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
