Submission #624639

#	Time	Username	Problem	Language	Result	Execution time	Memory
624639		MilosMilutinovic	Furniture (JOI20_furniture)	C++14	100 / 100	565 ms	28040 KiB

furniture

/**
 *    author:  wxhtzdy
 *    created: 03.08.2022 13:12:41
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }                
  vector<vector<bool>> dp(n, vector<bool>(m));
  dp[n - 1][m - 1] = true;  
  auto Update = [&](int i, int j) {
    if (a[i][j] == 1) {
      dp[i][j] = false;
      return;
    }
    dp[i][j] = false;
    if (i == n - 1 && j == m - 1) {
      dp[i][j] = true;
    }
    if (i + 1 < n) {
      dp[i][j] = dp[i][j] | dp[i + 1][j];
    }
    if (j + 1 < m) {
      dp[i][j] = dp[i][j] | dp[i][j + 1];
    }
  };
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      Update(i, j);
    }
  }
  vector<vector<vector<int>>> id(2, vector<vector<int>>(n, vector<int>(m, -1)));
  vector<vector<int>> path(2);
  { // right
    int T = 0;
    vector<int> que(1, 0);
    for (int b = 0; b < (int) que.size(); b++) {
      int x = que[b] / m;
      int y = que[b] % m;
      id[0][x][y] = T++;
      if (y < m - 1 && dp[x][y + 1]) {
        que.push_back(x * m + y + 1);
      } else if (x < n - 1) {
        que.push_back((x + 1) * m + y);
      }
    }
    path[0] = que;    
  }
  { // down
    int T = 0;
    vector<int> que(1, 0);
    for (int b = 0; b < (int) que.size(); b++) {
      int x = que[b] / m;
      int y = que[b] % m;
      id[1][x][y] = T++;
      if (x < n - 1 && dp[x + 1][y]) {
        que.push_back((x + 1) * m + y);
      } else if (y < m - 1) {
        que.push_back(x * m + y + 1);
      }
    }
    path[1] = que;    
  }
  auto Go0 = [&](int sx, int sy) {
    int T = id[0][sx][sy];
    for (int b = T; b < (int) path[0].size(); b++) {
      int x = path[0][b] / m;
      int y = path[0][b] % m;
      id[0][x][y] = b;
      if (y + 1 < m && dp[x][y + 1]) {
        path[0].push_back(x * m + y + 1);
      } else if (x + 1 < n) {
        path[0].push_back((x + 1) * m + y);
      }
    }
  };
  auto Go1 = [&](int sx, int sy) {
    int T = id[1][sx][sy];
    for (int b = T; b < (int) path[1].size(); b++) {
      int x = path[1][b] / m;
      int y = path[1][b] % m;
      id[1][x][y] = b;
      if (x + 1 < n && dp[x + 1][y]) {
        path[1].push_back((x + 1) * m + y);
      } else if (y + 1 < m) {
        path[1].push_back(x * m + y + 1);
      }
    }
  };
  function<void(int, int, bool)> Go = [&](int x, int y, bool fir) {
    if (x < 0 || y < 0) {
      return;
    }
    bool f0 = dp[x][y];
    Update(x, y);
    bool f1 = dp[x][y];
    if (!fir && f0 == f1) {
      return;
    }
    Go(x - 1, y, false);
    Go(x, y - 1, false);
  };
  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    bool f0 = (id[0][x][y] == -1);
    bool f1 = (id[1][x][y] == -1);
    if (f0 && f1) {
      cout << 1 << '\n';
      a[x][y] = 1;
      Go(x, y, true);
      continue;
    }
    if (!f0 & !f1) {
      cout << 0 << '\n';
      continue;
    }
    cout << 1 << '\n';
    a[x][y] = 1;
    Go(x, y, true);
    if (!f0) {
      int nx = path[0][id[0][x][y] - 1] / m;              
      int ny = path[0][id[0][x][y] - 1] % m;              
      while (path[0].back() != nx * m + ny) {
        id[0][path[0].back() / m][path[0].back() % m] = -1;
        path[0].pop_back();        
      }
      while (!dp[path[0].back() / m][path[0].back() % m]) {
        id[0][path[0].back() / m][path[0].back() % m] = -1;
        path[0].pop_back();
      }
      nx = path[0].back() / m;
      ny = path[0].back() % m;
      Go0(nx, ny);
    }
    if (!f1) {
      int nx = path[1][id[1][x][y] - 1] / m;              
      int ny = path[1][id[1][x][y] - 1] % m;              
      while (path[1].back() != nx * m + ny) {
        id[1][path[1].back() / m][path[1].back() % m] = -1;
        path[1].pop_back();        
      }
      while (!dp[path[1].back() / m][path[1].back() % m]) {
        id[1][path[1].back() / m][path[1].back() % m] = -1;
        path[1].pop_back();
      }
      nx = path[1].back() / m;
      ny = path[1].back() % m;
      Go1(nx, ny);
    }
  }                                                
  return 0;
}                          

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