Submission #1191937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191937		Seb	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	832 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

using vll = vector<ll>;
using pll = pair<ll,ll>;

#define pb push_back
#define MP make_pair
#define f first
#define s second
#define mid ((l+r)>>1)
#define SZ(x) (int)(x.size())
#define MP make_pair
#define all(x) x.begin(), x.end()

const ll MAXN = 1e3 + 5;
const ll MOD = 998244353;
const ll INF = 1e16;

vector<pll> aux;
ll grid[MAXN][MAXN];
bool vis[MAXN][MAXN];
ll N, M;
ll t;

void borra_nodos() {
    while (!aux.empty()) {
        auto p = aux.back();
        aux.pop_back();
        if (vis[p.f][p.s]) continue;

        grid[p.f][p.s] = 0;
        vis[p.f][p.s] = true;

        if (p.f) {
            grid[p.f - 1][p.s] &= 1;
            if (!grid[p.f - 1][p.s]) aux.pb(MP(p.f - 1, p.s));
        }
        if (p.s) {
            grid[p.f][p.s - 1] &= 2;
            if (!grid[p.f][p.s - 1]) aux.pb(MP(p.f, p.s - 1));
        }
    }
}

bool dfs(ll x, ll y, ll a = 0, ll b = 0) {
    if (a == N - 1 && b == M - 1) return true;
    if (!t || (x == a && y == b)) return false;
    t--;

    if (grid[a][b]&1 && b < M - 1 && dfs(x, y, a, b + 1)) return true;
    if (grid[a][b]&2 && a < N - 1 && dfs(x, y, a + 1, b)) return true;
    return false;
}

void tc() {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++) {
        ll a; cin >> a;
        grid[i][j] = 3;
        if (a) aux.pb(MP(i, j));
    }

    borra_nodos();

    ll Q; cin >> Q;
    while (Q--) {
        ll x, y; cin >> x >> y;

        t = 2100;
        if (dfs(x - 1, y - 1)) {
            aux.pb(MP(x - 1, y - 1));

            borra_nodos();

            cout << "1\n";
        }

        else cout << "0\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    while (t--) tc();
    return 0;
}

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