Submission #791171

#	Time	Username	Problem	Language	Result	Execution time	Memory
791171		makanhulia	Furniture (JOI20_furniture)	C++17	100 / 100	275 ms	25560 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl "\n"
#define pii pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define pque priority_queue
#define pqueg priority_queue<ll,vector<ll>,greater<ll>>
#define que queue<ll>
#define FOR(m,i,n) for(int i=(m); i<=(n); i++)
#define FORM(m,i,n) for(int i=(m); i>=(n); i--)
#define all(v) sort(v.begin(),v.end())
ll n,m,qq,x,y;
queue<pii> q;
ll grid[1010][1010],d[1000100];
bool vis[1010][1010];
vector<pii> v,vd;
bool cek;
void bfs() {
  cek = false;
  while(!q.empty()) {
    pii x = q.front();
    q.pop();
    d[x.fi+x.se]--;
    vd.pb({x.fi,x.se});
    if(d[x.fi+x.se] == 0) {
      cek = true;
      return;
    }
    if(vis[x.fi+1][x.se-1]) {
      if(!vis[x.fi+1][x.se]) {
        q.push({x.fi+1,x.se});
        vis[x.fi+1][x.se] = true;
        v.pb({x.fi+1,x.se});
      }
      if(!vis[x.fi][x.se-1]) {
        q.push({x.fi,x.se-1});      
        vis[x.fi][x.se-1] = true;      
        v.pb({x.fi,x.se-1});
      }
    }
    if(vis[x.fi-1][x.se+1]) {
      if(!vis[x.fi][x.se+1]) {
        q.push({x.fi,x.se+1});
        vis[x.fi][x.se+1] = true;
        v.pb({x.fi,x.se+1});
      }
      if(!vis[x.fi-1][x.se]) {
        q.push({x.fi-1,x.se});
        vis[x.fi-1][x.se] = true;        
        v.pb({x.fi-1,x.se});
      }
    } 
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  FOR(1,i,n) {
    FOR(1,j,m) {
      cin >> grid[i][j];
      vis[i][j] = grid[i][j];
      if(vis[i][j]) q.push({i,j});
      d[i+j]++;
    } 
  }
  FOR(1,i,m) vis[0][i] = true;
  FOR(1,i,n) vis[i][0] = true;
  FOR(1,i,m) vis[n+1][i] = true;
  FOR(1,i,n) vis[i][m+1] = true;
  bfs();
  v.clear();
  vd.clear();
  cin >> qq;
  while(qq--) {
    cin >> x >> y;
    if(vis[x][y]) {
      cout << 1 << endl;
      continue;
    }
    vis[x][y] = true;
    q.push({x,y});
    v.pb({x,y});
    bfs();
    if(cek) {
      cout << 0 << endl;
      for(auto i : vd) d[i.fi+i.se]++;
      for(auto i : v) vis[i.fi][i.se] = false;
    }
    else {
      cout << 1 << endl;
    }
    v.clear();
    vd.clear();
  }
}

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