Submission #697365

#	Time	Username	Problem	Language	Result	Execution time	Memory
697365		Ninja_Kunai	Furniture (JOI20_furniture)	C++14	5 / 100	5056 ms	1336 KiB

furniture

/**
*    Author :  Nguyen Tuan Vu
*    Created : 08.02.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long Rand(long long l, long long r) {return l + rng() % (r - l + 1);}

void file(){
    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}

const int N = 1e3 + 5;
int n, m, a[N][N], nquery, cur, dd[N][N];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    file();
    cin >> n >> m;
    FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];

    const int Dx[] = {0, 1};
    const int Dy[] = {1, 0};

    int nquery; cin >> nquery;
    while (nquery--) {
    	int u, v; cin >> u >> v;
    	if (a[u][v] == 1) cout << 0 << '\n';
    	else {
    		a[u][v] = 1;
    		++cur;
    		auto bfs = [&] (int u, int v) {
    			queue <pair <int, int>> q;
    			q.push({u, v});
    			dd[u][v] = cur;

    			while (q.size()) {
    				int u = q.front().first;
    				int v = q.front().second;
    				q.pop();

    				if (u == n && v == m) break;
	    			REP(i, 2) {
	    				int x = u + Dx[i];
	    				int y = v + Dy[i];

	    				if (x >= 1 && x <= n && y >= 1 && y <= m && dd[x][y] != cur && a[x][y] == 0) {
	    					dd[x][y] = cur;
	    					q.push({x, y});
	    				}
	    			}
	    		}
    		};

    		bfs(1, 1);
    		if (dd[n][m] == cur) {
    			cout << 1 << '\n';
    		}
    		else {
    			a[u][v] = 0;
    			cout << 0 << '\n';
    		}
    	}
    }
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message (stderr)

furniture.cpp: In function 'void file()':
furniture.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95