oj.uz

Submission #573023

# Submission time Handle Problem Language Result Execution time Memory
573023 2022-06-05T16:19:34 Z urosk Furniture (JOI20_furniture) C++14
100 / 100
 701 ms 83652 KB 
//https://oj.uz/problem/view/JOI20_furniture
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 1005
ll n,m;
ll a[maxn][maxn];
bool vis[maxn][maxn];
set<pll> s[2*maxn];
void dfs(ll x,ll y){
    vis[x][y] = 1;
    if(s[x+y].find({x,y})!=s[x+y].end()) s[x+y].erase(s[x+y].find({x,y}));
    if(vis[x+1][y-1]){
        if(!vis[x+1][y]) dfs(x+1,y);
        if(!vis[x][y-1]) dfs(x,y-1);
    }
    if(vis[x-1][y+1]){
        if(!vis[x-1][y]) dfs(x-1,y);
        if(!vis[x][y+1]) dfs(x,y+1);
    }
    return;
}
int main(){
	daj_mi_malo_vremena
    cin >> n >> m;
    for(ll i = 0;i<=n+1;i++) for(ll j = 0;j<=m+1;j++) vis[i][j] = 1;
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++){
            cin >> a[i][j];
            if(a[i][j]==0){
                s[i+j].insert({i,j});
                vis[i][j] = 0;
            }
        }
    }
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++){
            if(i+j==2||i+j==n+m) continue;
            if(!vis[i][j]&&((vis[i-1][j]&&vis[i][j-1])||(vis[i+1][j]&&vis[i][j+1]))) dfs(i,j);
        }
    }
    ll q; cin >> q;
    while(q--){
        //here;
        ll x,y; cin >> x>> y;
        //for(ll i = 0;i<=n;i++) ceri(vis[i],0,m);
        if(vis[x][y]) cout<<1<<endl;
        else{
            if(sz(s[x+y])==1) cout<<0<<endl;
            else{
                cout<<1<<endl;
                dfs(x,y);
            }
        }
    }
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 4 ms 1452 KB Output is correct
5 Correct 5 ms 1620 KB Output is correct
6 Correct 5 ms 1708 KB Output is correct
7 Correct 7 ms 1708 KB Output is correct
8 Correct 4 ms 1620 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 4 ms 1452 KB Output is correct
5 Correct 5 ms 1620 KB Output is correct
6 Correct 5 ms 1708 KB Output is correct
7 Correct 7 ms 1708 KB Output is correct
8 Correct 4 ms 1620 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct
10 Correct 16 ms 4312 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 635 ms 69344 KB Output is correct
13 Correct 350 ms 58700 KB Output is correct
14 Correct 701 ms 70776 KB Output is correct
15 Correct 649 ms 71564 KB Output is correct
16 Correct 543 ms 77164 KB Output is correct
17 Correct 583 ms 81104 KB Output is correct
18 Correct 643 ms 78960 KB Output is correct
19 Correct 532 ms 83440 KB Output is correct
20 Correct 537 ms 83652 KB Output is correct
21 Correct 554 ms 83512 KB Output is correct