Submission #576751

#	Time	Username	Problem	Language	Result	Execution time	Memory
576751		Pety	Furniture (JOI20_furniture)	C++14	100 / 100	304 ms	19828 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

int n, m, road[1002][1002], c[1002][1002], cnt[2002];

bool check1 (int i, int j) {
  if (i == 1 && j == 1)
    return 0;
  return (i == 1 || road[i - 1][j]) && (j == 1 || road[i][j - 1]);
}

bool check2 (int i, int j) {
  if (i == n && j == m)
    return 0;
  return (i == n || road[i + 1][j]) && (j == m || road[i][j + 1]);
}


int add (int i, int j) {
  if (road[i][j])
    return 1;
  if (cnt[i + j] == 1) 
    return 0;
  road[i][j] = 1;
  queue<pair<int, int>>q;
  q.push({i, j});
  cnt[i + j]--;
  while (q.size()) {
    auto p = q.front();
    q.pop();
    if (p.first < n && !road[p.first + 1][p.second] && check1(p.first + 1, p.second)) {
      road[p.first + 1][p.second] = 1;
      cnt[p.first + p.second + 1]--;
      q.push({p.first + 1, p.second});
    }
    if (p.second < m && !road[p.first][p.second + 1] && check1(p.first, p.second + 1)) {
      road[p.first][p.second + 1] = 1;
      cnt[p.first + p.second + 1]--;
      q.push({p.first, p.second + 1});
    }
  }
  q.push({i, j});
  while (q.size()) {
    auto p = q.front();
    q.pop();
    if (p.first > 1 && !road[p.first - 1][p.second] && check2(p.first - 1, p.second)) {
      road[p.first - 1][p.second] = 1;
      cnt[p.first + p.second - 1]--;
      q.push({p.first - 1, p.second});
    }
    if (p.second > 1 && !road[p.first][p.second - 1] && check2(p.first, p.second - 1)) {
      road[p.first][p.second - 1] = 1;
      cnt[p.first + p.second - 1]--;
      q.push({p.first, p.second - 1});
    }
  }
  return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) {
        cin >> c[i][j];
        cnt[i + j]++;
      }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        if (c[i][j]) {
            add(i, j);
        }
    int q;
    cin >> q;
    while (q--) {
      int x, y;
      cin >> x >> y;
      cout << add(x, y) << "\n";
    }
    return 0;
}

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