Submission #843966

#	Time	Username	Problem	Language	Result	Execution time	Memory
843966		mickey080929	Dangerous Skating (JOI16_skating)	C++17	100 / 100	68 ms	43108 KiB

skating

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int inf = 1e9;

int n, m;
int sx, sy, ex, ey;
int A[1010][1010];
pii L[1010][1010], R[1010][1010], U[1010][1010], D[1010][1010];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int vis[1010][1010];
char in[2000010];

int main() {
    fread(in, 1, sizeof(in), stdin);
    int T = 0;
    for (T=0; in[T] != ' '; T++) n = n * 10 + in[T] - '0';
    for (T++; in[T] != '\n'; T++) m = m * 10 + in[T] - '0';
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            T ++;
            if (in[T] == '#') A[i][j] = 0;
            else A[i][j] = 1;
        }
        T ++;
    }
    for (T++; in[T] != ' '; T++) sx = sx * 10 + in[T] - '0';
    for (T++; in[T] != '\n'; T++) sy = sy * 10 + in[T] - '0';
    for (T++; in[T] != ' '; T++) ex = ex * 10 + in[T] - '0';
    for (T++; in[T] != '\n'; T++) ey = ey * 10 + in[T] - '0';
    for (int i=1; i<=n; i++) {
        int p = 1;
        for (int j=2; j<=m; j++) {
            if (!A[i][j]) p = j;
            else L[i][j] = {i, p+1};
        }
        p = m;
        for (int j=m-1; j>=1; j--) {
            if (!A[i][j]) p = j;
            else R[i][j] = {i, p-1};
        }
    }
    for (int j=1; j<=m; j++) {
        int p = 1;
        for (int i=2; i<=n; i++) {
            if (!A[i][j]) p = i;
            else U[i][j] = {p+1, j};
        }
        p = n;
        for (int i=n-1; i>=1; i--) {
            if (!A[i][j]) p = i;
            else D[i][j] = {p-1, j};
        }
    }
    vector<pii> q1, q2, q3;
    q1.push_back({sx, sy});
    vis[sx][sy] = 1;
    int t = 0;
    while (!q1.empty() || !q2.empty()) {
        for (auto &[x, y] : q1) {
            if (x == ex && y == ey) {
                printf("%d\n", t);
                return 0;
            }
            for (auto &[nx, ny] : {L[x][y], R[x][y], U[x][y], D[x][y]}) {
                if (vis[nx][ny]) continue;
                vis[nx][ny] = 1;
                q2.push_back({nx, ny});
            }
        }
        for (auto &[x, y] : q1) {
            for (int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (!A[nx][ny]) continue;
                if (vis[nx][ny]) continue;
                vis[nx][ny] = 1;
                q3.push_back({nx, ny});
            }
        }
        q1 = q2;
        q2 = q3;
        q3.clear();
        t ++;
    }
    printf("-1\n");
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:24:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     fread(in, 1, sizeof(in), stdin);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22