oj.uz

Submission #790687

# Submission time Handle Problem Language Result Execution time Memory
790687 2023-07-23T06:03:41 Z andecaandeci Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 13604 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl "\n"
#define pii pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define pque priority_queue
#define pqueg priority_queue<ll,vector<ll>,greater<ll>>
#define que queue<ll>
#define FOR(m,i,n) for(int i=(m); i<=(n); i++)
#define FORM(m,i,n) for(int i=(m); i>=(n); i--)
#define all(v) sort(v.begin(),v.end())
ll n,m,qq,x,y;
queue<pii> q;
ll grid[1010][1010],d[1000100];
bool vis[1010][1010];
bool tempvis[1010][1010];
ll tempd[1000100];
bool cek;
void bfs() {
  cek = false;
  while(!q.empty()) {
    pii x = q.front();
    q.pop();
    d[x.fi+x.se]--;
    if(d[x.fi+x.se] == 0) cek = true;
    if(vis[x.fi+1][x.se-1] && !vis[x.fi+1][x.se] && x.fi < n) {
      q.push({x.fi+1,x.se});
      vis[x.fi+1][x.se] = true;
    }
    if(vis[x.fi-1][x.se+1] && !vis[x.fi][x.se+1] && x.se < m) {
      q.push({x.fi,x.se+1});
      vis[x.fi][x.se+1] = true;
    }  
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  FOR(1,i,n) {
    FOR(1,j,m) {
      cin >> grid[i][j];
      vis[i][j] = grid[i][j];
      if(vis[i][j]) q.push({i,j});
      d[i+j]++;
    } 
  }
  FOR(1,i,m) vis[0][i] = true;
  FOR(1,i,n) vis[i][0] = true;
  bfs();
  cin >> qq;
  while(qq--) {
    cin >> x >> y;
    if(vis[x][y]) cout << 1 << endl;
    else {
      FOR(1,i,n) {
        FOR(1,j,m) {
          tempvis[i][j] = vis[i][j];
          tempd[i+j] = d[i+j]; 
        }
      }
      q.push({x,y});
      vis[x][y] = true;
      bfs();
      if(cek) {
        cout << 0 << endl;
        FOR(1,i,n) {
          FOR(1,j,m) {
            vis[i][j] = tempvis[i][j];
            d[i+j] = tempd[i+j];
          }
        }
      }
      else {
        cout << 1 << endl;
      }
    }
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 8 ms 1116 KB Output is correct
7 Correct 7 ms 1048 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 11 ms 1108 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 8 ms 1116 KB Output is correct
7 Correct 7 ms 1048 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 11 ms 1108 KB Output is correct
10 Correct 65 ms 1348 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Execution timed out 5076 ms 13604 KB Time limit exceeded
13 Halted 0 ms 0 KB -