oj.uz

Submission #684095

# Submission time Handle Problem Language Result Execution time Memory
684095 2023-01-20T11:04:47 Z Darren0724 Furniture (JOI20_furniture) C++17
100 / 100
 1417 ms 15976 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> cnt(2050);
vector<vector<int>> v;
void dfs(int a,int b){
    v[a][b]=1;
    cnt[a+b]--;
    if(v[a-1][b+1]){
        if(v[a][b+1]==0){
            dfs(a,b+1);
        }
        if(v[a-1][b]==0){
            dfs(a-1,b);
        }
    }
    if(v[a+1][b-1]){
        if(v[a+1][b]==0){
            dfs(a+1,b);
        }
        if(v[a][b-1]==0){
            dfs(a,b-1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    v.resize(n+2,vector<int>(m+2,1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cnt[i+j]++;
            v[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int p;cin>>p;
            if(p==1){
                if(v[i][j]==0){
                    dfs(i,j);
                }
            }
        }
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        if(v[a][b]==1){
            cout<<1<<endl;
            continue;
        }
        if(cnt[a+b]<=1){
            cout<<0<<endl;
        }
        else{
            cout<<1<<endl;
            dfs(a,b);
        }

    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<v[i][j]<<' ';
        }
        cout<<endl;
    }
    */

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 14 ms 448 KB Output is correct
5 Correct 12 ms 340 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 14 ms 468 KB Output is correct
8 Correct 13 ms 468 KB Output is correct
9 Correct 14 ms 472 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 14 ms 448 KB Output is correct
5 Correct 12 ms 340 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 14 ms 468 KB Output is correct
8 Correct 13 ms 468 KB Output is correct
9 Correct 14 ms 472 KB Output is correct
10 Correct 34 ms 916 KB Output is correct
11 Correct 8 ms 436 KB Output is correct
12 Correct 444 ms 8752 KB Output is correct
13 Correct 60 ms 5640 KB Output is correct
14 Correct 1175 ms 13436 KB Output is correct
15 Correct 1162 ms 13520 KB Output is correct
16 Correct 1306 ms 14796 KB Output is correct
17 Correct 1380 ms 15464 KB Output is correct
18 Correct 1274 ms 14916 KB Output is correct
19 Correct 1411 ms 15976 KB Output is correct
20 Correct 1320 ms 15804 KB Output is correct
21 Correct 1417 ms 15796 KB Output is correct