Submission #293352

#	Time	Username	Problem	Language	Result	Execution time	Memory
293352		Mamnoon_Siam	Furniture (JOI20_furniture)	C++17	100 / 100	509 ms	8440 KiB

furniture

// #pragma gcc optimize("O3,unroll-loops")
// #pragma gcc target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)v.size()
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

const int N = 1e3 + 2;

namespace UR {
  int n, m;
  bool vis[N][N], on_path[N][N];
  vector<ii> path, extended_path;
  void set_nm(int x, int y) {
    // swap(x, y);
    n = x, m = y;
  }
  void set_cell(int x, int y, int value) {
    // swap(x, y);
    vis[x][y] = value;
  }
  bool get_on_path(int x, int y) {
    // swap(x, y);
    return on_path[x][y];
  }
  ii prv(int x, int y) {
    if(on_path[x-1][y]) return {x-1, y};
    if(on_path[x][y-1]) return {x, y-1};
    assert(false);
  }
  int nxt(int x, int y) {
    if(on_path[x+1][y]) return 2;
    if(on_path[x][y+1]) return 1;
    assert(false);
  }
  int dfs(int x, int y) {
    // cerr << "dfs " << x << ' ' << y << endl;
    if(x > n or y > m) return 0;
    if(x == n and y == m) {
      on_path[x][y] = 1;
      extended_path.emplace_back(n, m);
      return 1;
    }
    if(!vis[x][y+1]) {
      int ret = dfs(x, y+1);
      if(ret) {
        on_path[x][y] = 1;
        extended_path.emplace_back(x, y);
        return 1;
      }
    }
    if(!vis[x+1][y]) {
      int ret = dfs(x+1, y);
      if(ret) {
        on_path[x][y] = 1;
        extended_path.emplace_back(x, y);
        return 1;
      }
    }
    vis[x][y] = 1;
    return 0;
  }
  void update(int x, int y) {
    vis[x][y] = 1;
    bool flag = 0;
    int p, q;
    tie(p, q) = ii(x, y);
    int cnt = 10;
    while(p != 1 or q != 1) {
      tie(p, q) = prv(p, q);
      if(nxt(p, q) == 2) {
        continue;
      }
      int pp = p+1, qq = q;
      if(!vis[pp][qq] and dfs(pp, qq)) {
        while(path.back() != ii(p, q)) {
          ii pa = path.back();
          on_path[pa.fi][pa.se] = 0;
          // vis[pa.fi][pa.se] = 1; // CHECK THIS!
          path.pop_back();
        }
        while(extended_path.size()) {
          ii pa = extended_path.back();
          path.push_back(pa);
          on_path[pa.fi][pa.se] = 1;
          extended_path.pop_back();
        }
        flag = true;
        break;
      }
    }
    assert(flag);
  }
  void init() {
    dfs(1, 1);
    path = extended_path;
    reverse(all(path));
    extended_path.clear();
  }
  void destroy(int x, int y) {
    // swap(x, y);
    if(!on_path[x][y]) {
      vis[x][y] = 1;
      return;
    }
    update(x, y);
  }
}

namespace LL {
  int n, m;
  bool vis[N][N], on_path[N][N];
  vector<ii> path, extended_path;
  void set_nm(int x, int y) {
    swap(x, y);
    n = x, m = y;
  }
  void set_cell(int x, int y, int value) {
    swap(x, y);
    vis[x][y] = value;
  }
  bool get_on_path(int x, int y) {
    swap(x, y);
    return on_path[x][y];
  }
  ii prv(int x, int y) {
    if(on_path[x-1][y]) return {x-1, y};
    if(on_path[x][y-1]) return {x, y-1};
    assert(false);
  }
  int nxt(int x, int y) {
    if(on_path[x+1][y]) return 2;
    if(on_path[x][y+1]) return 1;
    assert(false);
  }
  int dfs(int x, int y) {
    // cerr << "dfs> " << x << ' ' << y << endl;
    if(x > n or y > m) return 0;
    if(x == n and y == m) {
      on_path[x][y] = 1;
      extended_path.emplace_back(n, m);
      return 1;
    }
    if(!vis[x][y+1]) {
      int ret = dfs(x, y+1);
      if(ret) {
        on_path[x][y] = 1;
        extended_path.emplace_back(x, y);
        return 1;
      }
    }
    if(!vis[x+1][y]) {
      int ret = dfs(x+1, y);
      if(ret) {
        on_path[x][y] = 1;
        extended_path.emplace_back(x, y);
        return 1;
      }
    }
    vis[x][y] = 1;
    return 0;
  }
  void update(int x, int y) {
    vis[x][y] = 1;
    bool flag = 0;
    int p, q;
    tie(p, q) = ii(x, y);
    int cnt = 10;
    while(p != 1 or q != 1) {
      tie(p, q) = prv(p, q);
      if(nxt(p, q) == 2) {
        continue;
      }
      int pp = p+1, qq = q;
      if(!vis[pp][qq] and dfs(pp, qq)) {
        while(path.back() != ii(p, q)) {
          ii pa = path.back();
          on_path[pa.fi][pa.se] = 0;
          // vis[pa.fi][pa.se] = 1; // CHECK THIS!
          path.pop_back();
        }
        while(extended_path.size()) {
          ii pa = extended_path.back();
          path.push_back(pa);
          on_path[pa.fi][pa.se] = 1;
          extended_path.pop_back();
        }
        flag = true;
        break;
      }
    }
    /*if(!flag) {
      cerr << x << ' ' << y << endl;

    }*/
    assert(flag);
  }
  void init() {
    dfs(1, 1);
    path = extended_path;
    reverse(all(path));
    extended_path.clear();
  }
  void destroy(int x, int y) {
    swap(x, y);
    if(!on_path[x][y]) {
      vis[x][y] = 1;
      return;
    }
    update(x, y);
  }
}

// int n, m, g[N][N];
char out[2 * N * N];
int ptr = 0;
// bool on_path[N][N];
// int vis[N][N];

// vector<ii> extended_path, path;

int n, m;
template<typename T>
void print_arr(T arr[N][N]) {
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; ++j) {
      cerr << arr[i][j];
    } cerr << endl;
  }
}

/*ii prv(int x, int y) {
  if(on_path[x-1][y]) return {x-1, y};
  if(on_path[x][y-1]) return {x, y-1};
  // cerr << x << ' ' << y << endl;
  assert(false);
}
int nxt(int x, int y) {
  if(on_path[x+1][y]) return 2;
  if(on_path[x][y+1]) return 1;
  assert(false);
}

int dfs(int x, int y) {
  // cerr << "dfs " << x << ' ' << y << endl;
  if(x == n and y == m) {
    on_path[x][y] = 1;
    extended_path.emplace_back(n, m);
    return 1;
  }
  if(!vis[x][y+1]) {
    int ret = dfs(x, y+1);
    if(ret) {
      on_path[x][y] = 1;
      extended_path.emplace_back(x, y);
      return 1;
    }
  }
  if(!vis[x+1][y]) {
    int ret = dfs(x+1, y);
    if(ret) {
      on_path[x][y] = 1;
      extended_path.emplace_back(x, y);
      return 1;
    }
  }
  vis[x][y] = 1;
  return 0;
}

void update(int x, int y) {
  vis[x][y] = 1;
  bool flag = 0;
  int p, q;
  tie(p, q) = prv(x, y);
  do {
    place : ;
    // cerr << '\t' << "pq = " << p << ' ' << q << endl;
    if(nxt(p, q) == 2) {
      if(p == 1 and q == 1){
        break;
      }
      tie(p, q) = prv(p, q);
      goto place;
    }
    int pp = p+1, qq = q;
    if(!vis[pp][qq] and dfs(pp, qq)) {
      // cerr << "\tgot it!" << endl;
      while(path.back() != ii(p, q)) {
        ii pa = path.back();
        on_path[pa.fi][pa.se] = 0;
        path.pop_back();
      }
      while(extended_path.size()) {
        ii pa = extended_path.back();
        path.push_back(pa);
        on_path[pa.fi][pa.se] = 1;
        extended_path.pop_back();
      }
      flag = true;
      break;
    }
  } while(p != 1 or q != 1);
  if(!flag) vis[x][y] = 0;
  // cerr << "flag = " << flag << endl;
  // if(x == 2 and y == 2) vis[2][1] = 0;
  return flag;
}*/

inline void print(bool wot) {
  out[ptr++] = wot ? '1' : '0';
  out[ptr++] = '\n';
}

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d", &UR::n, &UR::m);
  LL::set_nm(UR::n, UR::m);

  n = UR::n, m = UR::m;

  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; ++j) {
      int x; scanf("%d", &x);
      UR::set_cell(i, j, x);
      LL::set_cell(i, j, x);
    }
  }
  for(int i = 0; i <= n+1; ++i) {
    // vis[i][0] = vis[i][m+1] = 1;
    UR::set_cell(i, 0, 1);
    UR::set_cell(i, m+1, 1);
    LL::set_cell(i, 0, 1);
    LL::set_cell(i, m+1, 1);
  }
  for(int i = 0; i <= n+1; ++i) {
    // vis[0][i] = vis[n+1][i] = 1;
    UR::set_cell(0, i, 1);
    UR::set_cell(n+1, i, 1);
    LL::set_cell(0, i, 1);
    LL::set_cell(n+1, i, 1);
  }
  int q; scanf("%d", &q);

  /*dfs(1, 1);
  path = extended_path;
  reverse(all(path));
  extended_path.clear();*/

  UR::init();
  LL::init();

  /*cerr << "UR vis:\n";
  print_arr(UR::vis);
  cerr << "UR on_path:\n";
  print_arr(UR::on_path);*/

  /*cerr << "LL vis:\n";
  print_arr(LL::vis);
  cerr << "LL on_path:\n";
  print_arr(LL::on_path);*/

  // print_arr(on_path);

  while(q--) {
    int x, y;
    scanf("%d %d", &x, &y);
    if(UR::get_on_path(x, y) and LL::get_on_path(x, y)) {
      print(false);
    } else {
      UR::destroy(x, y);
      LL::destroy(x, y);
      print(true);
    }
    // cerr << "Another query completed:" << endl;

    /*cerr << "UR vis:\n";
    print_arr(UR::vis);
    cerr << "UR on_path:\n";
    print_arr(UR::on_path);*/

    /*cerr << "LL vis:\n";
    print_arr(LL::vis);
    cerr << "LL on_path:\n";
    print_arr(LL::on_path);*/

    /*if(!on_path[x][y]) {
      print(true);
      // cerr << "true" << endl;
      vis[x][y] = 1;
    } else {
      // cerr << "on path!" << endl;
      print(update(x, y));
      // cerr << "false" << endl;
    }
    // cerr << "path ----> " << endl;
    // print_arr(on_path);
    // cerr << "vis ----> " << endl;
    // print_arr(vis);*/
  }
  out[ptr++] = '\0';
  printf("%s", out);
  return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'void UR::update(int, int)':
furniture.cpp:76:9: warning: unused variable 'cnt' [-Wunused-variable]
   76 |     int cnt = 10;
      |         ^~~
furniture.cpp: In function 'void LL::update(int, int)':
furniture.cpp:176:9: warning: unused variable 'cnt' [-Wunused-variable]
  176 |     int cnt = 10;
      |         ^~~
furniture.cpp: In function 'int main(int, const char**)':
furniture.cpp:328:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  328 |   scanf("%d %d", &UR::n, &UR::m);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:335:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  335 |       int x; scanf("%d", &x);
      |              ~~~~~^~~~~~~~~~
furniture.cpp:354:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  354 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~
furniture.cpp:378:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  378 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~

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