Submission #976720

#	Time	Username	Problem	Language	Result	Execution time	Memory
976720		eblabrada	Portals (BOI14_portals)	C++17	100 / 100	560 ms	112500 KiB

portals

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
  #include "algo/debug.h"
#else
  #define debug(...) 42
#endif

using ll = long long;
using db = long double; // or double, if TL is tight
// #define int ll

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(v) (int)((v).size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back

const int N = 1000;
const int INF = 1e8;

using T = tuple<int, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;

const int xdir[4] = {1, 0, -1, 0}, ydir[4] = {0, 1, 0, -1};
char a[N + 3][N + 3];
int dis[N + 3][N + 3], pdis[N + 3][N + 3];
vector<pair<int, int>> adj[N + 3][N + 3];
pair<int, int> st, en;
queue<pair<int, int>> q;

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  for (int i = 0; i <= N + 1; i++) {
    for (int j = 0; j <= N + 1; j++) {
      a[i][j] = '#';
    }
  }

  int n, m; cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];

      if (a[i][j] == 'S') st = {i, j};
      if (a[i][j] == 'C') en = {i, j};
    }
  }


  for (int i = 1; i <= n; i++) {
    int last = 0;
    for (int j = 1; j <= m; j++) {
      if (a[i][j] == '#') {
        last = j;
      } else {
        adj[i][j].push_back({i, last + 1});
        for (int d = 0; d < 4; d++) {
          int ni = i + xdir[d], nj = j + ydir[d];
          adj[i][j].push_back({ni, nj});
        }  
      }
    }

    last = m + 1;
    for (int j = m; j >= 1; j--) {
      if (a[i][j] == '#') {
        last = j;
      } else {
        adj[i][j].push_back({i, last - 1});
      }
    }
  }

  for (int j = 1; j <= m; j++) {
    int last = 0;
    for (int i = 1; i <= n; i++) {
      if (a[i][j] == '#') {
        last = i;
      } else {
        adj[i][j].push_back({last + 1, j});
      }
    }

    last = n + 1;
    for (int i = n; i >= 1; i--) {
      if (a[i][j] == '#') {
        last = i;
      } else {
        adj[i][j].push_back({last - 1, j});
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      pdis[i][j] = INF;

      bool found = false;
      for (int d = 0; d < 4; d++) {
        int ni = i + xdir[d], nj = j + ydir[d];
        if (a[ni][nj] == '#') {
          found = true;
        }
      }

      if (found) {
        pdis[i][j] = 0;
        q.push({i, j});
      }
    }
  }

  while (!q.empty()) {
    auto [x, y] = q.front(); q.pop();
    for (auto &[nx, ny]: adj[x][y]) {
      if (pdis[nx][ny] == INF) {
        pdis[nx][ny] = pdis[x][y] + 1;
        q.push({nx, ny});
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      dis[i][j] = INF;
    }
  }
  
  pq.push({0, st.f, st.s}); dis[st.f][st.s] = 0;
  while (!pq.empty()) {
    auto [d, x, y] = pq.top(); pq.pop();
    if (pair(x, y) == en) {
      return cout << d << "\n", 0;
    }
    if (dis[x][y] < d) continue;
    for (auto [nx, ny]: adj[x][y]) {
      int newCost = d;
      if (abs(nx - x) == 1 || abs(ny - y) == 1) {
        newCost += 1;
      } else {
        newCost += pdis[x][y] + 1;
      }
      if (dis[nx][ny] > newCost) {
        dis[nx][ny] = newCost;
        pq.push({newCost, nx, ny});
      }
    }
  }

} 

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