Submission #1092787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092787		12345678	Furniture (JOI20_furniture)	C++17	100 / 100	228 ms	31568 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95