Submission #673534

#	Time	Username	Problem	Language	Result	Execution time	Memory
673534		taher	Portals (BOI14_portals)	C++17	100 / 100	245 ms	14440 KiB

portals

#include <bits/stdc++.h>

using namespace std;

const int inf = 1000000000;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n , m;
  cin >> n >> m;
  vector<vector<char>> g(n , vector<char> (m));
  for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < m ; j++) {
      cin >> g[i][j];
    }
  }
  vector<vector<int>> prefX(n , vector<int> (m));
  vector<vector<int>> prefY(m , vector<int> (n));
  for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < m ; j++) {
      if (j > 0) prefX[i][j] = prefX[i][j - 1];
      if (g[i][j] == '#') prefX[i][j] += 1;
    }
  }
  for (int j = 0 ; j < m ; j++) {
    for (int i = 0 ; i < n ; i++) {
      if (i > 0) prefY[j][i] = prefY[j][i - 1];
      if (g[i][j] == '#') prefY[j][i] += 1;      
    }
  }
  int locX = 0 , locY = 0;
  int desX = 0 , desY = 0;
  for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < m ; j++) {
      if (g[i][j] == 'S') {
        locX = i;
        locY = j;
      }
      if (g[i][j] == 'C') {
        desX = i;
        desY = j;
      }
    }
  }
  auto Ok = [&](int i , int j) {
    if (i >= 0 && i < n && j >= 0 && j < m) {
      return true;
    } 
    return false;
  };
  auto Up = [&](int i , int j) {
    int lo = 0 , hi = i - 1;
    int at = prefY[j][i];
    if (at == 0) return -1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (prefY[j][mid] < at) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return lo;
  };
  auto Down = [&](int i , int j) {
    int lo = i + 1 , hi = n - 1;
    int at = prefY[j][n - 1] - prefY[j][i];
    if (at == 0) return n;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (prefY[j][n - 1] - prefY[j][mid] == at) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return lo;
  };

  auto Left = [&](int i , int j) {
    int lo = 0 , hi = j - 1;
    int at = prefX[i][j];
    if (at == 0) return -1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (prefX[i][mid] < at) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return lo;
  };

  auto Right = [&](int i , int j) {
    int lo = j + 1 , hi = m - 1;
    int at = prefX[i][m - 1] - prefX[i][j];
    if (at == 0) return m;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (prefX[i][m - 1] - prefX[i][mid] == at) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return lo;
  };

  const int dx[4] = {1 , 0 , 0 , -1};
  const int dy[4] = {0 , 1 , -1 , 0};
  #define pi pair<int , int>
  priority_queue<pair<int , pi> , vector<pair<int , pi>> , greater<pair<int , pi>>> que;
  que.emplace(0 , make_pair(locX , locY));
  vector<vector<int>> dist(n , vector<int> (m , inf));
  dist[locX][locY] = 0;

  auto Update = [&](int i , int j , int ni , int nj , int add) {
    if (dist[ni][nj] > dist[i][j] + add) {
      dist[ni][nj] = dist[i][j] + add;
      que.emplace(dist[ni][nj] , make_pair(ni , nj));
    }
    return ;
  };
  while (!que.empty()) {
    auto pos = que.top();
    que.pop();
    int x = pos.second.first;
    int y = pos.second.second;
    if (dist[x][y] != pos.first) {
      continue;
    }
    for (int it = 0 ; it < 4 ; it++) {
      int nx = x + dx[it];
      int ny = y + dy[it];
      if (Ok(nx , ny)) {
        if (g[nx][ny] != '#' && dist[nx][ny] > dist[x][y] + 1) {
          dist[nx][ny] = dist[x][y] + 1;
          que.emplace(dist[nx][ny] , make_pair(nx , ny));
        }
      }
    }
    int x0 = Up(x , y);
    int x1 = Down(x , y);
    int y0 = Left(x , y);
    int y1 = Right(x , y);
    int d0 = x - x0;
    int d1 = x1 - x;
    int d2 = y - y0;
    int d3 = y1 - y;
    int d = min({d0 , d1 , d2 , d3});
    if (Ok(x0 + 1 , y)) {
      if (d < d0) {
        assert(g[x0 + 1][y] != '#');
        Update(x , y , x0 + 1 , y , d);
      }
    }
    if (Ok(x1 - 1 , y)) {
      if (d < d1) {
        assert(g[x1 - 1][y] != '#');
        Update(x , y , x1 - 1 , y , d);
      }
    }
    if (Ok(x , y0 + 1)) {
      if (d < d2) {
        assert(g[x][y0 + 1] != '#');
        Update(x , y , x , y0 + 1 , d);
      }
    }
    if (Ok(x , y1 - 1)) {
      if (d < d3) {
        assert(g[x][y1 - 1] != '#');
        Update(x , y , x , y1 - 1 , d);
      }
    }
  }
  cout << dist[desX][desY] << '\n';
  return 0;  
}

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30