oj.uz

Submission #1013901

# Submission time Handle Problem Language Result Execution time Memory
1013901 2024-07-04T07:58:32 Z Baytoro Furniture (JOI20_furniture) C++17
100 / 100
 1461 ms 16256 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
//#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
int n,m;
int a[1005][1005],diag[100005];
vector<int> dx={1,-1,0,0},
            dy={0,0,1,-1};
void bfs(int x, int y) {
    if(a[x][y]==1) return;
    diag[x+y]--;
    a[x][y]=1;
    for(int i=0;i<4;i++) {
        int X=x+dx[i],Y=y+dy[i];
        if(!a[X][Y] && ((a[X-1][Y] && a[X][Y-1] && !(X==1 && Y==1)) || (a[X+1][Y] && a[X][Y+1] && !(X==n && Y==m)))) {
            bfs(X,Y);
        }
    }

}
void solve() {
    cin>>n>>m;
    vector<pair<int,int>> v;
    memset(a,1,sizeof a);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            //cin>>a[i][j];
            int x;cin>>x;
            if(x) v.pb({i,j});
            diag[i+j]++;
            a[i][j]=0;
        }
    }
    for(auto it: v)
        bfs(it.fr,it.sc);
    /*for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }*/
    int q;cin>>q;
    while(q--) {
        int x,y;cin>>x>>y;
        if(a[x][y]) {
            cout<<1<<endl;
            continue;
        }
        if(diag[x+y]==1) {
            cout<<0<<endl;
            continue;
        }
        cout<<1<<endl;
        bfs(x,y);
    }
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 9 ms 4652 KB Output is correct
3 Correct 7 ms 4440 KB Output is correct
4 Correct 11 ms 4620 KB Output is correct
5 Correct 13 ms 4692 KB Output is correct
6 Correct 14 ms 4696 KB Output is correct
7 Correct 14 ms 4700 KB Output is correct
8 Correct 20 ms 4700 KB Output is correct
9 Correct 14 ms 4700 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 9 ms 4652 KB Output is correct
3 Correct 7 ms 4440 KB Output is correct
4 Correct 11 ms 4620 KB Output is correct
5 Correct 13 ms 4692 KB Output is correct
6 Correct 14 ms 4696 KB Output is correct
7 Correct 14 ms 4700 KB Output is correct
8 Correct 20 ms 4700 KB Output is correct
9 Correct 14 ms 4700 KB Output is correct
10 Correct 49 ms 5040 KB Output is correct
11 Correct 9 ms 4696 KB Output is correct
12 Correct 465 ms 9744 KB Output is correct
13 Correct 111 ms 7364 KB Output is correct
14 Correct 1140 ms 14640 KB Output is correct
15 Correct 1113 ms 14412 KB Output is correct
16 Correct 1200 ms 15188 KB Output is correct
17 Correct 1447 ms 15620 KB Output is correct
18 Correct 1461 ms 15520 KB Output is correct
19 Correct 1420 ms 16184 KB Output is correct
20 Correct 1267 ms 16256 KB Output is correct
21 Correct 1300 ms 16232 KB Output is correct