oj.uz

Submission #1092787

# Submission time Handle Problem Language Result Execution time Memory
1092787 2024-09-25T05:54:56 Z 12345678 Furniture (JOI20_furniture) C++17
100 / 100
 228 ms 31568 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int n, m, q, x, y, c[nx][nx], vs[nx][nx], vsrv[nx][nx], in[nx][nx], out[nx][nx], layer[2*nx];

bool calc(int i, int j)
{
    if (!vs[i][j]) return 0;
    in[i][j]=out[i][j]=0;
    if (i!=1&&vs[i-1][j]) in[i][j]++;
    if (j!=1&&vs[i][j-1]) in[i][j]++;
    if (i!=n&&vs[i+1][j]) out[i][j]++;
    if (j!=m&&vs[i][j+1]) out[i][j]++;
    if ((i==1&&j==1)||(i==n&&j==m)) return 0;
    return min(in[i][j], out[i][j])==0;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>c[i][j];
    vs[1][1]=1;
    vsrv[n][m]=1;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (!(i==1&&j==1)&&!c[i][j]) vs[i][j]=vs[i-1][j]||vs[i][j-1];
    for (int i=n; i>=1; i--) for (int j=m; j>=1; j--) if (!(i==n&&j==m)&&!c[i][j]) vsrv[i][j]=vsrv[i+1][j]||vsrv[i][j+1];
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) vs[i][j]=vs[i][j]&&vsrv[i][j];
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (vs[i][j]) layer[i+j]++, calc(i, j);
    cin>>q;
    while (q--)
    {
        cin>>x>>y;
        if (!vs[x][y]) cout<<1<<'\n';
        else
        {
            if (layer[x+y]==1) cout<<0<<'\n';
            else
            {
                cout<<1<<'\n';
                queue<pair<int, int>> q;
                vs[x][y]=0;
                layer[x+y]--;
                q.push({x, y});
                while (!q.empty())
                {
                    auto [a, b]=q.front();
                    q.pop();
                    if (a!=1&&calc(a-1, b)) vs[a-1][b]=0, layer[a-1+b]--, q.push({a-1, b});
                    if (b!=1&&calc(a, b-1)) vs[a][b-1]=0, layer[a+b-1]--, q.push({a, b-1});
                    if (a!=n&&calc(a+1, b)) vs[a+1][b]=0, layer[a+1+b]--, q.push({a+1, b});
                    if (b!=m&&calc(a, b+1)) vs[a][b+1]=0, layer[a+b+1]--, q.push({a, b+1});
                }
            }
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2136 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2144 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 4 ms 2544 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2136 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2144 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 4 ms 2544 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 6 ms 1884 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 127 ms 24536 KB Output is correct
13 Correct 52 ms 21072 KB Output is correct
14 Correct 193 ms 28240 KB Output is correct
15 Correct 187 ms 28476 KB Output is correct
16 Correct 219 ms 29728 KB Output is correct
17 Correct 217 ms 31048 KB Output is correct
18 Correct 228 ms 30292 KB Output is correct
19 Correct 209 ms 31492 KB Output is correct
20 Correct 198 ms 31568 KB Output is correct
21 Correct 208 ms 31568 KB Output is correct