oj.uz

Submission #516610

# Submission time Handle Problem Language Result Execution time Memory
516610 2022-01-21T15:07:43 Z terrasphere Furniture (JOI20_furniture) C++17
5 / 100
 7 ms 1888 KB 
#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=m;j>=1;j--)
            {
                x[i]+=k[i-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

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 956 KB Output is correct
2 Correct 2 ms 1228 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 4 ms 1356 KB Output is correct
7 Correct 6 ms 1356 KB Output is correct
8 Correct 4 ms 1284 KB Output is correct
9 Correct 4 ms 1356 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 956 KB Output is correct
2 Correct 2 ms 1228 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 4 ms 1356 KB Output is correct
7 Correct 6 ms 1356 KB Output is correct
8 Correct 4 ms 1284 KB Output is correct
9 Correct 4 ms 1356 KB Output is correct
10 Runtime error 7 ms 1888 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -