Submission #784535

#	Time	Username	Problem	Language	Result	Execution time	Memory
784535		makanhulia	Furniture (JOI20_furniture)	C++17	100 / 100	210 ms	14092 KiB

furniture

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long, long long>

int n,m,q,diagonal[2069];
bool grid[1069][1069],valid[1069][1069];

void dfs(int x, int y)
{
    if(valid[x][y]) return;
    diagonal[x+y] -= 1;
    valid[x][y] = 1;
    // jika grid[i][j] = 1, maka :
    // 1. grid[i+1][j] dan grid[i][j-1] bisa jadi 1 asalkan grid[i-1][j+1] = 1
    // 2. grid[i-1][j] dan grid[i][j+1] bisa jadi 1 asalkan grid[i+1][j-1] = 1
    if(valid[x-1][y+1])
    {
        // if(!valid[x-1][y])
        // {
            dfs(x-1,y);
        // }
        // if(!valid[x][y+1])
        // {
            dfs(x,y+1);
        // }
    }
    if(valid[x+1][y-1])
    {
        // if(!valid[x][y-1])
        // {
            dfs(x,y-1);
        // }
        // if(!valid[x+1][y])
        // {
            dfs(x+1,y);
        // }
    }

}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            ++diagonal[i+j];
        }
    }
    for(i=0;i<=m+1;i++)
    {
        // atas
        valid[0][i] = 1;
        // bawah
        valid[n+1][i] = 1;                                                                                                              
    }
    for(i=0;i<=n+1;i++)
    {
        // kanan
        valid[i][m+1] = 1;
        // kiri
        valid[i][0] = 1;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>grid[i][j];
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(grid[i][j])
            {
                dfs(i,j);
            }
        }
    }
    // cout<<"debug : \n";
    // for(i=1;i<=n+1;i++)
    // {
    //     for(j=1;j<=m+1;j++)
    //     {
    //         cout<<grid[i][j]<<(j == m+1 ? '\n':' ');
    //     }
    // }
    // cout<<"query : \n";
     cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(valid[x][y])
        {
            cout<<1<<'\n';
            continue;
        }
        if(diagonal[x+y] == 1)
        {
            cout<<0<<'\n';
            continue;
        }
        cout<<1<<'\n';
        dfs(x,y);
    }
}

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