oj.uz

Submission #516614

# Submission time Handle Problem Language Result Execution time Memory
516614 2022-01-21T15:25:49 Z terrasphere Furniture (JOI20_furniture) C++17
5 / 100
 12 ms 3032 KB 
#include <bits/stdc++.h>

using namespace std;

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

queue<pair<int,int>> que1;
queue<pair<int,int>> que2;

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

void BFS2()
{
    que2.push({n,m});
    a2[n][m]=true;
    while(!que2.empty())
    {
        pair<int,int> c;
        c=que2.front();
        que2.pop();
        if(c.second-1>=1 && arr[c.first][c.second-1]==0 && !visited2[c.first][c.second-1])
        {
            que2.push({c.first,c.second-1});
            visited2[c.first][c.second-1]=true;
            a2[c.first][c.second-1]=true;
        }
        if(c.first-1>=1 && arr[c.first-1][c.second]==0 && !visited2[c.first-1][c.second])
        {
            que2.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;j>=1;j--)
            {
                x[i]+=k[j][i-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>=1 && 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>=1 && 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:131:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
furniture.cpp:134:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |             scanf("%d",&arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:139:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
furniture.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2248 KB Output is correct
2 Correct 3 ms 2776 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 ms 2776 KB Output is correct
5 Correct 7 ms 3032 KB Output is correct
6 Correct 5 ms 3032 KB Output is correct
7 Correct 5 ms 3032 KB Output is correct
8 Correct 4 ms 2972 KB Output is correct
9 Correct 5 ms 3032 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2248 KB Output is correct
2 Correct 3 ms 2776 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 ms 2776 KB Output is correct
5 Correct 7 ms 3032 KB Output is correct
6 Correct 5 ms 3032 KB Output is correct
7 Correct 5 ms 3032 KB Output is correct
8 Correct 4 ms 2972 KB Output is correct
9 Correct 5 ms 3032 KB Output is correct
10 Incorrect 12 ms 2328 KB Output isn't correct
11 Halted 0 ms 0 KB -