제출 #790687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790687		andecaandeci	Furniture (JOI20_furniture)	C++17	5 / 100	5076 ms	13604 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];
bool tempvis[1010][1010];
ll tempd[1000100];
bool cek;
void bfs() {
  cek = false;
  while(!q.empty()) {
    pii x = q.front();
    q.pop();
    d[x.fi+x.se]--;
    if(d[x.fi+x.se] == 0) cek = true;
    if(vis[x.fi+1][x.se-1] && !vis[x.fi+1][x.se] && x.fi < n) {
      q.push({x.fi+1,x.se});
      vis[x.fi+1][x.se] = true;
    }
    if(vis[x.fi-1][x.se+1] && !vis[x.fi][x.se+1] && x.se < m) {
      q.push({x.fi,x.se+1});
      vis[x.fi][x.se+1] = true;
    }  
  }
}
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;
  bfs();
  cin >> qq;
  while(qq--) {
    cin >> x >> y;
    if(vis[x][y]) cout << 1 << endl;
    else {
      FOR(1,i,n) {
        FOR(1,j,m) {
          tempvis[i][j] = vis[i][j];
          tempd[i+j] = d[i+j]; 
        }
      }
      q.push({x,y});
      vis[x][y] = true;
      bfs();
      if(cek) {
        cout << 0 << endl;
        FOR(1,i,n) {
          FOR(1,j,m) {
            vis[i][j] = tempvis[i][j];
            d[i+j] = tempd[i+j];
          }
        }
      }
      else {
        cout << 1 << endl;
      }
    }
  }
}

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