Submission #791169

#TimeUsernameProblemLanguageResultExecution timeMemory
791169makanhuliaFurniture (JOI20_furniture)C++17
0 / 100
2 ms980 KiB
#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]; vector<pii> v,vd; bool cek; void bfs() { cek = false; while(!q.empty()) { pii x = q.front(); q.pop(); d[x.fi+x.se]--; vd.pb({x.fi,x.se}); if(d[x.fi+x.se] == 0) { cek = true; return; } if(vis[x.fi+1][x.se-1] && x.fi < n) { if(!vis[x.fi+1][x.se]) { q.push({x.fi+1,x.se}); vis[x.fi+1][x.se] = true; v.pb({x.fi+1,x.se}); } if(!vis[x.fi][x.se-1]) { q.push({x.fi,x.se-1}); vis[x.fi][x.se-1] = true; v.pb({x.fi,x.se-1}); } } if(vis[x.fi-1][x.se+1] && x.se < m) { if(!vis[x.fi][x.se+1]) { q.push({x.fi,x.se+1}); vis[x.fi][x.se+1] = true; v.pb({x.fi,x.se+1}); } if(!vis[x.fi-1][x.se]) { q.push({x.fi-1,x.se}); vis[x.fi-1][x.se] = true; v.pb({x.fi-1,x.se}); } } } } 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; FOR(1,i,m) vis[n+1][i] = true; FOR(1,i,n) vis[i][m+1] = true; bfs(); v.clear(); vd.clear(); cin >> qq; while(qq--) { cin >> x >> y; if(vis[x][y]) { cout << 1 << endl; continue; } vis[x][y] = true; q.push({x,y}); v.pb({x,y}); bfs(); if(cek) { cout << 0 << endl; for(auto i : vd) d[i.fi+i.se]++; for(auto i : v) vis[i.fi][i.se] = false; } else { cout << 1 << endl; } v.clear(); vd.clear(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...