Submission #1144560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144560		Perl32	Furniture (JOI20_furniture)	C++20	0 / 100	5 ms	8772 KiB

furniture

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template<typename T> using normal_queue = priority_queue<T, vector<T>, less<>>;

constexpr int inf = 0x3f3f3f3f;

const int maxN = 1e3;
int a[maxN][maxN], dp[maxN][maxN];
bool used[maxN][maxN];
pair<int, int> pa[maxN][maxN];

int dx[2] = {1, 0};
int dy[2] = {0, 1};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    memset(a, inf, sizeof a);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x;
            cin >> x;
            if (x == 1) {
                a[i][j] = 0;
            }
        }
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        a[x][y] = i;
    }
    auto valid = [&](int x, int y) { return x > -1 && y > -1 && x < n && y < m; };
    memset(dp, -1, sizeof dp);
    normal_queue<array<int, 3>> pq;
    dp[0][0] = a[0][0];
    pq.push({dp[0][0], 0, 0});
    pa[0][0] = {-1, -1};
    while (!pq.empty()) {
        auto [mn, x, y] = pq.top(); pq.pop();
        if (used[x][y]) continue;
        used[x][y] = 1;
        for (int j = 0; j < 2; ++j) {
            int cx = x + dx[j], cy = y + dy[j];
            if (valid(cx, cy) && dp[cx][cy] < min(a[x][y], dp[x][y])) {
                pa[cx][cy] = {x, y};
                dp[cx][cy] = min(a[x][y], dp[x][y]);
                pq.push({dp[cx][cy], cx, cy});
            }
        }
    };
    int x = n - 1, y = m - 1;
    vector<int> ans(q + 1, 1);
    while (x != -1 && y != -1) {
        if (a[x][y] > 0 && a[x][y] < inf) ans[a[x][y]] = 0;
        int nx = pa[x][y].first, ny = pa[x][y].second;
        x = nx, y = ny;
    }
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

/*

 */

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