Submission #516604

#	Time	Username	Problem	Language	Result	Execution time	Memory
516604		terrasphere	Furniture (JOI20_furniture)	C++17	0 / 100	2 ms	1228 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

int arr[1111][1111];
int n,m;
bool visited1[1111][1111];
bool visited2[1111][1111];
bool a1[1111][1111];
bool a2[1111][1111];
bool k[1111][1111];
int x[3333];

queue<pair<int,int>> que;

void BFS1()
{
    que.push({1,1});
    a1[1][1]=true;
    while(!que.empty())
    {
        pair<int,int> c;
        c=que.front();
        que.pop();
        if(c.second+1<=m && arr[c.first][c.second+1]==0 && !visited1[c.first][c.second+1])
        {
            que.push({c.first,c.second+1});
            visited1[c.first][c.second+1]=true;
            a1[c.first][c.second+1]=true;
        }
        if(c.first+1<=n && arr[c.first+1][c.second]==0 && !visited1[c.first+1][c.second])
        {
            que.push({c.first+1,c.second});
            visited1[c.first+1][c.second]=true;
            a1[c.first+1][c.second]=true;
        }
    }
    return;
}

void BFS2()
{
    que.push({n,m});
    a2[n][m]=true;
    while(!que.empty())
    {
        pair<int,int> c;
        c=que.front();
        que.pop();
        if(c.second-1>=0 && arr[c.first][c.second-1]==0 && !visited2[c.first][c.second-1])
        {
            que.push({c.first,c.second-1});
            visited2[c.first][c.second-1]=true;
            a2[c.first][c.second-1]=true;
        }
        if(c.first-1>=0 && arr[c.first-1][c.second]==0 && !visited2[c.first-1][c.second])
        {
            que.push({c.first-1,c.second});
            visited2[c.first-1][c.second]=true;
            a2[c.first-1][c.second]=true;
        }
    }
    return;
}

void fill_k()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            k[i][j]=a1[i][j]&a2[i][j];
        }
    }
    return;
}

void fill_x()
{
    for(int i=2;i<=n+m;i++)
    {
        if(i<=n+1)
        {
            for(int j=i-1;j>=1;j--)
            {
                x[i]+=k[j][i-j];
            }
        }
        else
        {
            for(int j=n-1;j>=1;j--)
            {
                x[i]+=k[n-j][j];
            }
        }
    }
    return;
}

void del(int a,int b)
{
    x[a+b]--;
    k[a][b]=false;
    if(a+1<=n && k[a+1][b])
    {
        if(b==1 || !k[a+1][b-1])
            del(a+1,b);
    }
    if(a-1>=0 && k[a-1][b])
    {
        if(b==n || !k[a-1][b+1])
            del(a-1,b);
    }
    if(b+1<=m && k[a][b+1])
    {
        if(a==1 || !k[a-1][b+1])
            del(a,b+1);
    }
    if(b-1>=0 && k[a][b-1])
    {
        if(a==n || !k[a+1][b-1])
            del(a,b-1);
    }
    return;
}

int main()
{
    int q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&arr[i][j]);
    BFS1();
    BFS2();
    fill_k();
    fill_x();
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(!k[a][b])
            printf("1\n");
        else if(x[a+b]<=1)
            printf("0\n");
        else
        {
            printf("1\n");
            del(a,b);
        }
    }
    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
furniture.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |             scanf("%d",&arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
furniture.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

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