Submission #968906

#TimeUsernameProblemLanguageResultExecution timeMemory
968906happy_nodeFurniture (JOI20_furniture)C++17
100 / 100
1307 ms22668 KiB
#include <bits/stdc++.h> using namespace std; const int MX=1005; int N,M,Q; int C[MX][MX], deg[MX][MX], rdeg[MX][MX], cnt[2*MX]; bool good[MX][MX]; void dfs(int x, int y) { if(x+1<=N && !C[x+1][y]) { deg[x+1][y]-=1; if(deg[x+1][y]==0) { if(good[x+1][y]) cnt[x+1+y-2]-=1; good[x+1][y]=0; C[x+1][y]=1; dfs(x+1,y); } } if(y+1<=M && !C[x][y+1]) { deg[x][y+1]-=1; if(deg[x][y+1]==0) { if(good[x][y+1]) cnt[x+y+1-2]-=1; good[x][y+1]=0; C[x][y+1]=1; dfs(x,y+1); } } } void rdfs(int x, int y) { if(x-1>=1 && !C[x-1][y]) { rdeg[x-1][y]-=1; if(rdeg[x-1][y]==0) { if(good[x-1][y]) cnt[x-1+y-2]-=1; good[x-1][y]=0; C[x-1][y]=1; rdfs(x-1,y); } } if(y-1>=1 && !C[x][y-1]) { rdeg[x][y-1]-=1; if(rdeg[x][y-1]==0) { if(good[x][y-1]) cnt[x+y-1-2]-=1; good[x][y-1]=0; C[x][y-1]=1; rdfs(x,y-1); } } } bool r[MX][MX], rr[MX][MX]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin>>N>>M; for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { cin>>C[i][j]; } } r[1][1]=1; for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { if(C[i][j]) continue; if(!r[i][j]) continue; r[i+1][j]|=r[i][j]; r[i][j+1]|=r[i][j]; deg[i][j+1]+=1; deg[i+1][j]+=1; } } rr[N][M]=1; for(int i=N;i>=1;i--) { for(int j=M;j>=1;j--) { if(C[i][j]) continue; if(!rr[i][j]) continue; rr[i-1][j]|=rr[i][j]; rr[i][j-1]|=rr[i][j]; rdeg[i-1][j]+=1; rdeg[i][j-1]+=1; } } for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { if(C[i][j]) { r[i][j]=0; rr[i][j]=0; } } } for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { if(r[i][j] && rr[i][j]) { good[i][j]=1; cnt[i+j-2]+=1; } } } cin>>Q; for(int i=1;i<=Q;i++) { int x,y; cin>>x>>y; if(!good[x][y]) { cout<<1<<endl; continue; } if(cnt[x+y-2]==1) { cout<<0<<endl; continue; } good[x][y]=0; cnt[x+y-2]-=1; C[x][y]=1; dfs(x,y); rdfs(x,y); cout<<1<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...