oj.uz

Submission #794159

# Submission time Handle Problem Language Result Execution time Memory
794159 2023-07-26T10:00:48 Z gun_gan Portals (BOI14_portals) C++17
100 / 100
 720 ms 147560 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 1005;

string grid[MX];
int N, M;
vector<array<int,3>> g[MX][MX];
int dist[MX][MX]; // distance to the closest wall
int sx = 0, sy = 0, ex = 0, ey = 0;

void bfs() {
      for(int i = 0; i < MX; i++)
            for(int j = 0; j < MX; j++)
                  dist[i][j] = 1e9;

      queue<pair<int,int>> q;
      
      for(int i = 0; i < N; i++) {
            for(int j = 0; j < MX; j++) {
                  if(grid[i][j] == '#') continue;

                  bool adj = 0;
                  adj |= i - 1 < 0 || grid[i - 1][j] == '#';
                  adj |= i + 1 >= N || grid[i + 1][j] == '#';
                  adj |= j - 1 < 0 || grid[i][j - 1] == '#';
                  adj |= j + 1 >= M || grid[i][j + 1] == '#';

                  if(adj) {
                        q.push({i, j});
                        dist[i][j] = 1;
                  }
            }
      }

      while(!q.empty()) {
            auto [x, y] = q.front(); q.pop();

            for(auto [nx, ny, w] : g[x][y]) {
                  if(dist[nx][ny] == 1e9) {
                        dist[nx][ny] = dist[x][y] + 1;
                        q.push({nx, ny});
                  }
            }
      }
}

void dijkstra() {
      for(int i = 0; i < MX; i++)
            for(int j = 0; j < MX; j++)
                  dist[i][j] = 1e9;

      priority_queue<pair<int, pair<int,int> > > pq;

      pq.push({0, {sx, sy}});

      while(!pq.empty()) {
            auto [cost, p] = pq.top(); pq.pop();
            cost = -cost;
            auto [x, y] = p;
            if(dist[x][y] < cost) continue;

            for(auto [nx, ny, w] : g[x][y]) {
                  if(dist[nx][ny] > cost + w) {
                        dist[nx][ny] = cost + w;
                        pq.push({-(cost + w), {nx, ny}});
                  }
            }
      }
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N >> M;
      
      for(int i = 0; i < N; i++) {
            cin >> grid[i];
            for(int j = 0; j < M; j++) {
                  if(grid[i][j] == 'S') {
                        sx = i, sy = j;
                  }
                  if(grid[i][j] == 'C') {
                        ex = i, ey = j;
                  }     
            }
      }

      for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                  if(i - 1 >= 0 && grid[i - 1][j] != '#') g[i][j].push_back({i - 1, j, 1});
                  if(i + 1 < N && grid[i + 1][j] != '#') g[i][j].push_back({i + 1, j, 1});
                  if(j - 1 >= 0 && grid[i][j - 1] != '#') g[i][j].push_back({i, j - 1, 1});
                  if(j + 1 < M && grid[i][j + 1] != '#') g[i][j].push_back({i, j + 1, 1});
            }
      }

      bfs();

      for(int i = 0; i < N; i++) {
            set<int> st;
            for(int j = 0; j < M; j++) 
                  if(grid[i][j] == '#') st.insert(j);

            st.insert(M);

            vector<int> lf(M), rg(M);

            for(int j = 0; j < M; j++) {
                  if(grid[i][j] == '#') {
                        st.erase(j);
                        continue;
                  }

                  rg[j] = *st.begin();
                  // g[i][j].push_back({i, *st.begin() - 1});
            }

            st.clear(); 

            st.insert(-1);  

            for(int j = 0; j < M; j++) {
                  if(grid[i][j] == '#') {
                        st.insert(j);
                        continue;
                  }

                  lf[j] = *st.rbegin();
                  // g[i][j].push_back({i, *st.rbegin() + 1});
            }

            for(int j = 0; j < M; j++) {
                  if(grid[i][j] == '#') continue;

                  g[i][j].push_back({i, rg[j] - 1, dist[i][j]});
                  g[i][j].push_back({i, lf[j] + 1, dist[i][j]});
            }
      }

      for(int j = 0; j < M; j++) {
            set<int> st;
            for(int i = 0; i < N; i ++) 
                  if(grid[i][j] == '#') st.insert(i);

            st.insert(N);

            vector<int> lf(N), rg(N);

            for(int i = 0; i < N; i++) {
                  if(grid[i][j] == '#') {
                        st.erase(i);
                        continue;
                  }

                  rg[i] = *st.begin();
                  // g[i][j].push_back({*st.begin() - 1, j});
            }            

            st.clear();

            st.insert(-1);

            for(int i = 0; i < N; i++) {
                  if(grid[i][j] == '#') {
                        st.insert(i);
                        continue;
                  }

                  lf[i] = *st.rbegin();
                  // g[i][j].push_back({*st.rbegin() + 1, j});
            }

            for(int i = 0; i < N; i++) {
                  if(grid[i][j] == '#') continue;
                  g[i][j].push_back({rg[i] - 1, j, dist[i][j]});
                  g[i][j].push_back({lf[i] + 1, j, dist[i][j]});
            }
      }

      dijkstra();

      cout << dist[ex][ey] << '\n';      
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27988 KB Output is correct
2 Correct 14 ms 27988 KB Output is correct
3 Correct 15 ms 28084 KB Output is correct
4 Correct 14 ms 28020 KB Output is correct
5 Correct 14 ms 28052 KB Output is correct
6 Correct 14 ms 28044 KB Output is correct
7 Correct 14 ms 27988 KB Output is correct
8 Correct 14 ms 28116 KB Output is correct
9 Correct 14 ms 28044 KB Output is correct
10 Correct 14 ms 27988 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27988 KB Output is correct
2 Correct 15 ms 28060 KB Output is correct
3 Correct 14 ms 27988 KB Output is correct
4 Correct 15 ms 27972 KB Output is correct
5 Correct 14 ms 28056 KB Output is correct
6 Correct 15 ms 28052 KB Output is correct
7 Correct 14 ms 28060 KB Output is correct
8 Correct 14 ms 28116 KB Output is correct
9 Correct 15 ms 28560 KB Output is correct
10 Correct 16 ms 28568 KB Output is correct
11 Correct 16 ms 28344 KB Output is correct
12 Correct 16 ms 28436 KB Output is correct
13 Correct 15 ms 28372 KB Output is correct
14 Correct 14 ms 28056 KB Output is correct
15 Correct 16 ms 28436 KB Output is correct
16 Correct 14 ms 28056 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27972 KB Output is correct
2 Correct 18 ms 28056 KB Output is correct
3 Correct 17 ms 28052 KB Output is correct
4 Correct 14 ms 28116 KB Output is correct
5 Correct 35 ms 32140 KB Output is correct
6 Correct 34 ms 32180 KB Output is correct
7 Correct 34 ms 32236 KB Output is correct
8 Correct 29 ms 32740 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27916 KB Output is correct
2 Correct 14 ms 28116 KB Output is correct
3 Correct 14 ms 28116 KB Output is correct
4 Correct 14 ms 27956 KB Output is correct
5 Correct 15 ms 28116 KB Output is correct
6 Correct 17 ms 28052 KB Output is correct
7 Correct 16 ms 28080 KB Output is correct
8 Correct 14 ms 28116 KB Output is correct
9 Correct 15 ms 28500 KB Output is correct
10 Correct 16 ms 28500 KB Output is correct
11 Correct 16 ms 28372 KB Output is correct
12 Correct 16 ms 28432 KB Output is correct
13 Correct 18 ms 28488 KB Output is correct
14 Correct 33 ms 32084 KB Output is correct
15 Correct 34 ms 32248 KB Output is correct
16 Correct 32 ms 32252 KB Output is correct
17 Correct 35 ms 31768 KB Output is correct
18 Correct 34 ms 32572 KB Output is correct
19 Correct 32 ms 32528 KB Output is correct
20 Correct 38 ms 32480 KB Output is correct
21 Correct 32 ms 32212 KB Output is correct
22 Correct 33 ms 32212 KB Output is correct
23 Correct 35 ms 32252 KB Output is correct
24 Correct 31 ms 32480 KB Output is correct
25 Correct 15 ms 28060 KB Output is correct
26 Correct 16 ms 28372 KB Output is correct
27 Correct 13 ms 27988 KB Output is correct
28 Correct 29 ms 32644 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27924 KB Output is correct
2 Correct 15 ms 28112 KB Output is correct
3 Correct 15 ms 28108 KB Output is correct
4 Correct 14 ms 28056 KB Output is correct
5 Correct 14 ms 28052 KB Output is correct
6 Correct 14 ms 28088 KB Output is correct
7 Correct 14 ms 28020 KB Output is correct
8 Correct 14 ms 28116 KB Output is correct
9 Correct 16 ms 28500 KB Output is correct
10 Correct 17 ms 28480 KB Output is correct
11 Correct 16 ms 28436 KB Output is correct
12 Correct 16 ms 28436 KB Output is correct
13 Correct 16 ms 28372 KB Output is correct
14 Correct 33 ms 32060 KB Output is correct
15 Correct 33 ms 32180 KB Output is correct
16 Correct 33 ms 32284 KB Output is correct
17 Correct 33 ms 31812 KB Output is correct
18 Correct 33 ms 32460 KB Output is correct
19 Correct 33 ms 32532 KB Output is correct
20 Correct 30 ms 32468 KB Output is correct
21 Correct 33 ms 32212 KB Output is correct
22 Correct 34 ms 32208 KB Output is correct
23 Correct 34 ms 32340 KB Output is correct
24 Correct 619 ms 126152 KB Output is correct
25 Correct 655 ms 139936 KB Output is correct
26 Correct 607 ms 139960 KB Output is correct
27 Correct 589 ms 139852 KB Output is correct
28 Correct 702 ms 131140 KB Output is correct
29 Correct 720 ms 133516 KB Output is correct
30 Correct 689 ms 134156 KB Output is correct
31 Correct 31 ms 32468 KB Output is correct
32 Correct 597 ms 139828 KB Output is correct
33 Correct 14 ms 27988 KB Output is correct
34 Correct 16 ms 28372 KB Output is correct
35 Correct 567 ms 122196 KB Output is correct
36 Correct 14 ms 28116 KB Output is correct
37 Correct 28 ms 32684 KB Output is correct
38 Correct 498 ms 147560 KB Output is correct
39 Correct 525 ms 104576 KB Output is correct