oj.uz

Submission #784535

# Submission time Handle Problem Language Result Execution time Memory
784535 2023-07-16T08:08:57 Z makanhulia Furniture (JOI20_furniture) C++17
100 / 100
 210 ms 14092 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 7 ms 848 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 101 ms 7048 KB Output is correct
13 Correct 48 ms 4208 KB Output is correct
14 Correct 175 ms 11816 KB Output is correct
15 Correct 178 ms 12108 KB Output is correct
16 Correct 189 ms 12928 KB Output is correct
17 Correct 199 ms 13740 KB Output is correct
18 Correct 194 ms 13272 KB Output is correct
19 Correct 210 ms 13968 KB Output is correct
20 Correct 198 ms 14092 KB Output is correct
21 Correct 201 ms 13996 KB Output is correct