Submission #656480

#	Time	Username	Problem	Language	Result	Execution time	Memory
656480		600Mihnea	Portals (BOI14_portals)	C++17	100 / 100	351 ms	54668 KiB

portals

bool home = 0;
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> rev(vector<int> v, int ok) {
  if (ok) {
    reverse(v.begin(), v.end());
  }
  return v;
}

const int N = 1000 + 7;
const int INF = (int) 1e9 + 7;
int n;
int m;
int a[N][N];
int r1;
int c1;
int r2;
int c2;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int dwall[N][N];
int d[N][N];
pair<int, int> cell[N][N][4];

const int D = 2 * N;
vector<pair<int, int>> q[D];

signed main() {
  if (home == 0) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen ("___input___.txt", "r", stdin);
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      dwall[i][j] = d[i][j] = INF;
    }
  }


  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    assert((int) s.size() == m);
    for (int j = 1; j <= m; j++) {
      char ch = s[j - 1];
      assert(ch == '.' || ch == '#' || ch == 'S' || ch == 'C');
      if (ch != '#') {
        a[i][j] = 1;
      }
      if (ch == 'S') {
        assert(r1 == 0 && c1 == 0);
        r1 = i;
        c1 = j;
      }
      if (ch == 'C') {
        assert(r2 == 0 && c2 == 0);
        r2 = i;
        c2 = j;
      }
    }
  }
  vector<int> _on;
  vector<int> _om;
  for (int i = 1; i <= n; i++) {
    _on.push_back(i);
  }
  for (int i = 1; i <= m; i++) {
    _om.push_back(i);
  }
  {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (a[i][j]) {
          bool is_near_wall = 0;
          for (int k = 0; k < 4; k++) {
            int in = i + dr[k];
            int jn = j + dc[k];
            if (a[in][jn] == 0) {
              is_near_wall = 1;
            }
          }
          if (is_near_wall) {
            dwall[i][j] = 0;
          }
        }
      }
    }
    for (int step = 1; step <= 2; step++) {
      for (int revn = 0; revn <= 1; revn++) {
        for (int revm = 0; revm <= 1; revm++) {
          vector<int> on = rev(_on, revn);
          vector<int> om = rev(_om, revm);
          for (auto &r : on) {
            for (auto &c : om) {
              for (int k = 0; k < 4; k++) {
                int rn = r + dr[k];
                int cn = c + dc[k];
                dwall[r][c] = min(dwall[r][c], 1 + dwall[rn][cn]);
              }
            }
          }
        }
      }
    }
  }

  {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (a[i][j]) {
          for (int k = 0; k < 4; k++) {
            int in = i + dr[k];
            int jn = j + dc[k];
            if (a[in][jn] == 0) {
              cell[i][j][k] = {i, j};
            }
          }
        }
      }
    }
    for (int revn = 0; revn <= 1; revn++) {
      for (int revm = 0; revm <= 1; revm++) {
        vector<int> on = rev(_on, revn);
        vector<int> om = rev(_om, revm);
        for (auto &r : on) {
          for (auto &c : om) {
            for (int k = 0; k < 4; k++) {
              int rn = r + dr[k];
              int cn = c + dc[k];
              if (a[r][c] == 1 && a[rn][cn] == 1) {
                cell[r][c][k] = cell[rn][cn][k];
              }
            }
          }
        }
      }
    }
  }

  int maxd = 0;
  q[0].push_back({r1, c1});
  d[r1][c1] = 0;

  for (int ds = 0; ds <= maxd; ds++) {
    for (auto &cellx : q[ds % D]) {
      int i = cellx.first;
      int j = cellx.second;
      if (d[i][j] != ds) {
        continue;
      }
      for (int k = 0; k < 4; k++) {
        int in = i + dr[k];
        int jn = j + dc[k];
        if (a[in][jn] && d[i][j] + 1 < d[in][jn]) {
          d[in][jn] = d[i][j] + 1;
          q[d[in][jn] % D].push_back({in, jn});
          maxd = max(maxd, d[in][jn]);
        }
        in = cell[i][j][k].first;
        jn = cell[i][j][k].second;
        if (d[i][j] + dwall[i][j] + 1 < d[in][jn]) {
          d[in][jn] = d[i][j] + dwall[i][j] + 1;
          q[d[in][jn] % D].push_back({in, jn});
          maxd = max(maxd, d[in][jn]);
        }
      }
    }
    q[ds % D].clear();
  }
  cout << d[r2][c2] << "\n";

  return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:37:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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