oj.uz

Submission #941118

# Submission time Handle Problem Language Result Execution time Memory
941118 2024-03-08T07:23:46 Z Ghulam_Junaid Portals (BOI14_portals) C++17
100 / 100
 279 ms 51684 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
const int inf = 1e9 + 10;

int n, m, sx, sy, ex, ey, dist[N][N];
char mat[N][N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
//           U  R  D   L

vector<pair<int, int>> walls;
pair<int, int> max_move[N][N][4];
int wall_dist[N][N];

bool valid(int x, int y){
    return (x >= 0 and x < n and y >= 0 and y < m and mat[x][y] != '#');
}

void bfs(){
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            wall_dist[i][j] = min(min(i + 1, j + 1), min(n - i, m - j));

    queue<pair<int, int>> q;
    for (auto [x, y] : walls){
        wall_dist[x][y] = 0;
        q.push({x, y});
    }

    while (!q.empty()){
        auto p = q.front();
        q.pop();

        int x = p.first;
        int y = p.second;

        for (int d = 0; d < 4; d ++){
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (valid(nx, ny) and wall_dist[nx][ny] > wall_dist[x][y] + 1){
                wall_dist[nx][ny] = wall_dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

void dijkstra(){
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            dist[i][j] = inf;
    dist[sx][sy] = 0;

    set<pair<int, pair<int, int>>> st;
    st.insert({0, {sx, sy}});

    while (!st.empty()){
        auto X = *st.begin();
        st.erase(st.begin());
        
        int cur = X.first;
        auto p = X.second;

        int x = p.first;
        int y = p.second;

        for (int d = 0; d < 4; d ++){
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (valid(nx, ny) and dist[nx][ny] > dist[x][y] + 1){
                st.erase({dist[nx][ny], {nx, ny}});
                dist[nx][ny] = dist[x][y] + 1;
                st.insert({dist[nx][ny], {nx, ny}});
            }

            p = max_move[x][y][d];
            nx = p.first;
            ny = p.second;

            if (dist[nx][ny] > dist[x][y] + wall_dist[x][y]){
                st.erase({dist[nx][ny], {nx, ny}});
                dist[nx][ny] = dist[x][y] + wall_dist[x][y];
                st.insert({dist[nx][ny], {nx, ny}});
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < m; j ++){
            cin >> mat[i][j];
            if (mat[i][j] == 'S')
                sx = i, sy = j;
            if (mat[i][j] == 'C')
                ex = i, ey = j;
            if (mat[i][j] == '#')
                walls.push_back({i, j});
        }
    }

    bfs();

    for (int i = 0; i < n; i ++){
        for (int j = 0; j < m; j ++){
            if (mat[i][j] == '#')
                continue;

            if (valid(i - 1, j))
                max_move[i][j][0] = max_move[i - 1][j][0];
            else
                max_move[i][j][0] = {i, j};

            if (valid(i, j - 1))
                max_move[i][j][3] = max_move[i][j - 1][3];
            else
                max_move[i][j][3] = {i, j};
        }
    }

    for (int i = n - 1; i >= 0; i --){
        for (int j = m - 1; j >= 0; j --){
            if (mat[i][j] == '#')
                continue;

            if (valid(i + 1, j))
                max_move[i][j][2] = max_move[i + 1][j][2];
            else
                max_move[i][j][2] = {i, j};

            if (valid(i, j + 1))
                max_move[i][j][1] = max_move[i][j + 1][1];
            else
                max_move[i][j][1] = {i, j};
        }
    }

    dijkstra();
    cout << dist[ex][ey] << endl;
}

Compilation message

portals.cpp: In function 'void dijkstra()':
portals.cpp:65:13: warning: unused variable 'cur' [-Wunused-variable]
   65 |         int cur = X.first;
      |             ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 10888 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 11 ms 15064 KB Output is correct
6 Correct 11 ms 15196 KB Output is correct
7 Correct 12 ms 15196 KB Output is correct
8 Correct 7 ms 15196 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10840 KB Output is correct
14 Correct 9 ms 15320 KB Output is correct
15 Correct 10 ms 15196 KB Output is correct
16 Correct 10 ms 15312 KB Output is correct
17 Correct 10 ms 15128 KB Output is correct
18 Correct 12 ms 15048 KB Output is correct
19 Correct 14 ms 14940 KB Output is correct
20 Correct 10 ms 15004 KB Output is correct
21 Correct 9 ms 15316 KB Output is correct
22 Correct 10 ms 15308 KB Output is correct
23 Correct 10 ms 15192 KB Output is correct
24 Correct 8 ms 14940 KB Output is correct
25 Correct 1 ms 4568 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 1 ms 4440 KB Output is correct
28 Correct 8 ms 15308 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6500 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10840 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 9 ms 15320 KB Output is correct
15 Correct 10 ms 15196 KB Output is correct
16 Correct 15 ms 15196 KB Output is correct
17 Correct 9 ms 15196 KB Output is correct
18 Correct 15 ms 15252 KB Output is correct
19 Correct 10 ms 15072 KB Output is correct
20 Correct 9 ms 14940 KB Output is correct
21 Correct 9 ms 15356 KB Output is correct
22 Correct 10 ms 15196 KB Output is correct
23 Correct 10 ms 15352 KB Output is correct
24 Correct 219 ms 49612 KB Output is correct
25 Correct 279 ms 43092 KB Output is correct
26 Correct 230 ms 42500 KB Output is correct
27 Correct 228 ms 42804 KB Output is correct
28 Correct 175 ms 50352 KB Output is correct
29 Correct 223 ms 50320 KB Output is correct
30 Correct 250 ms 50172 KB Output is correct
31 Correct 9 ms 14936 KB Output is correct
32 Correct 253 ms 42424 KB Output is correct
33 Correct 1 ms 4440 KB Output is correct
34 Correct 3 ms 10844 KB Output is correct
35 Correct 213 ms 46336 KB Output is correct
36 Correct 1 ms 4440 KB Output is correct
37 Correct 6 ms 15196 KB Output is correct
38 Correct 127 ms 51684 KB Output is correct
39 Correct 132 ms 50312 KB Output is correct