Submission #928639

#	Time	Username	Problem	Language	Result	Execution time	Memory
928639		1075508020060209tc	Furniture (JOI20_furniture)	C++14	0 / 100	48 ms	134004 KiB

furniture

//#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 (stderr)

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){
      |          ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95