oj.uz

Submission #576751

# Submission time Handle Problem Language Result Execution time Memory
576751 2022-06-13T11:45:57 Z Pety Furniture (JOI20_furniture) C++14
100 / 100
 304 ms 19828 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 4 ms 1068 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 4 ms 1208 KB Output is correct
7 Correct 4 ms 1208 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 4 ms 1068 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 4 ms 1208 KB Output is correct
7 Correct 4 ms 1208 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 9 ms 1108 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 144 ms 12608 KB Output is correct
13 Correct 59 ms 9544 KB Output is correct
14 Correct 277 ms 17172 KB Output is correct
15 Correct 279 ms 17336 KB Output is correct
16 Correct 275 ms 18500 KB Output is correct
17 Correct 288 ms 19320 KB Output is correct
18 Correct 270 ms 18828 KB Output is correct
19 Correct 267 ms 19704 KB Output is correct
20 Correct 262 ms 19828 KB Output is correct
21 Correct 304 ms 19672 KB Output is correct