oj.uz

Submission #843951

# Submission time Handle Problem Language Result Execution time Memory
843951 2023-09-04T17:56:51 Z mickey080929 None (JOI16_skating) C++17
13 / 100
 3000 ms 21532 KB 
#include <bits/stdc++.h>

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 dist[1010][1010];

int main() {
    scanf("%d %d", &n, &m);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            char c;
            scanf(" %c", &c);
            if (c == '#') A[i][j] = 0;
            else A[i][j] = 1;
        }
    }
    scanf("%d %d", &sx, &sy);
    scanf("%d %d", &ex, &ey);
    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};
        }
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) dist[i][j] = inf;
    priority_queue<tuple<int,int,int>> pq;
    pq.push({0, sx, sy});
    dist[sx][sy] = 0;
    while (!pq.empty()) {
        auto [c, x, y] = pq.top();
        assert(1 <= x && x <= n && 1 <= y && y <= m);
        pq.pop();
        if (dist[x][y] < c) continue;
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!A[nx][ny]) continue;
            if (dist[nx][ny] <= c + 2) continue;
            dist[nx][ny] = c + 2;
            pq.push({c + 2, nx, ny});
        }
        for (auto [nx, ny] : {L[x][y], R[x][y], U[x][y], D[x][y]}) {
            if (!A[nx][ny]) continue;
            if (dist[nx][ny] <= c + 1) continue;
            dist[nx][ny] = c + 1;
            pq.push({c + 1, nx, ny});
        }
    }
    if (dist[ex][ey] >= inf) printf("-1\n");
    else printf("%d\n", dist[ex][ey]);
}

Compilation message

skating.cpp: In function 'int main()':
skating.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skating.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~
skating.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d %d", &sx, &sy);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
skating.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d", &ex, &ey);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10700 KB Output is correct
9 Correct 1 ms 10704 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10700 KB Output is correct
9 Correct 1 ms 10704 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Execution timed out 3040 ms 21532 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10700 KB Output is correct
9 Correct 1 ms 10704 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Execution timed out 3040 ms 21532 KB Time limit exceeded
12 Halted 0 ms 0 KB -