# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
553203 | 2022-04-25T04:37:14 Z | tht2005 | Furniture (JOI20_furniture) | C++17 | 336 ms | 18784 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1003; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; int n, m, cnt[N << 1], c[N][N]; bool f[N][N], g[N][N], r[N][N]; int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { scanf("%d", &c[i][j]); } } f[1][1] = 1; for(int i = 1; i <= n; ++i) { for(int j = 1 + (i == 1); j <= m; ++j) { if(c[i][j]) continue; f[i][j] = f[i - 1][j] || f[i][j - 1]; } } g[n][m] = 1; for(int i = n; i > 0; --i) { for(int j = m - (i == n); j > 0; --j) { if(c[i][j]) continue; g[i][j] = g[i + 1][j] || g[i][j + 1]; } } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { r[i][j] = f[i][j] && g[i][j]; if(r[i][j]) { ++cnt[i + j]; } } } r[0][1] = r[n + 1][m] = 1; int _; scanf("%d", &_); while(_--) { int x, y; scanf("%d %d", &x, &y); if(r[x][y]) { if(cnt[x + y] > 1) { queue<pair<int, int>> q; r[x][y] = 0; --cnt[x + y]; q.emplace(x, y); while(!q.empty()) { auto [u, v] = q.front(); q.pop(); for(int e = 0; e < 4; ++e) { int a = u + dx[e], b = v + dy[e]; if(a < 1 || a > n || b < 1 || b > m || !r[a][b]) continue; if((!r[a - 1][b] && !r[a][b - 1]) || (!r[a + 1][b] && !r[a][b + 1])) { r[a][b] = 0; --cnt[a + b]; q.emplace(a, b); } } } putchar('1'); } else { putchar('0'); } } else { putchar('1'); } putchar('\n'); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 724 KB | Output is correct |
2 | Correct | 2 ms | 980 KB | Output is correct |
3 | Correct | 2 ms | 872 KB | Output is correct |
4 | Correct | 3 ms | 1000 KB | Output is correct |
5 | Correct | 4 ms | 1088 KB | Output is correct |
6 | Correct | 4 ms | 1108 KB | Output is correct |
7 | Correct | 3 ms | 1088 KB | Output is correct |
8 | Correct | 3 ms | 1108 KB | Output is correct |
9 | Correct | 4 ms | 1108 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 724 KB | Output is correct |
2 | Correct | 2 ms | 980 KB | Output is correct |
3 | Correct | 2 ms | 872 KB | Output is correct |
4 | Correct | 3 ms | 1000 KB | Output is correct |
5 | Correct | 4 ms | 1088 KB | Output is correct |
6 | Correct | 4 ms | 1108 KB | Output is correct |
7 | Correct | 3 ms | 1088 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 | 956 KB | Output is correct |
11 | Correct | 3 ms | 608 KB | Output is correct |
12 | Correct | 162 ms | 11656 KB | Output is correct |
13 | Correct | 98 ms | 8664 KB | Output is correct |
14 | Correct | 248 ms | 16152 KB | Output is correct |
15 | Correct | 267 ms | 16456 KB | Output is correct |
16 | Correct | 242 ms | 17444 KB | Output is correct |
17 | Correct | 336 ms | 18348 KB | Output is correct |
18 | Correct | 271 ms | 17728 KB | Output is correct |
19 | Correct | 288 ms | 18648 KB | Output is correct |
20 | Correct | 279 ms | 18784 KB | Output is correct |
21 | Correct | 264 ms | 18624 KB | Output is correct |