Submission #794159

#	Time	Username	Problem	Language	Result	Execution time	Memory
794159		gun_gan	Portals (BOI14_portals)	C++17	100 / 100	720 ms	147560 KiB

portals

#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 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30