Submission #585077

#	Time	Username	Problem	Language	Result	Execution time	Memory
585077		MohammadAghil	Portals (BOI14_portals)	C++17	100 / 100	362 ms	85848 KiB

portals

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define pb push_back

const ll mod = 1e9+7, maxn = 1e3+2, inf = ll(1e9)+5;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dist_wall[maxn][maxn];
pp ad[maxn][maxn][4];
pp st, en;
bool wall[maxn][maxn];
int n, m;

void clc_bfs_wall(){
     deque<pp> q;
     rep(i,0,n+2) rep(j,0,m+2) {
          dist_wall[i][j] = inf;
          if(wall[i][j]) dist_wall[i][j] = 0, q.pb({i, j});
     }
     while(sz(q)){
          auto[i, j] = q.front(); q.pop_front();
          rep(d,0,4){
               int x = dx[d] + i, y = dy[d] + j;
               if(x > 0 && x <= n && y > 0 && y <= m && !wall[x][y] && dist_wall[x][y] == inf)
                    dist_wall[x][y] = dist_wall[i][j] + 1, q.pb({x, y});
          }
     }
}

vector<pair<int, pp>> adj(int i, int j){
     vector<pair<int, pp>> res;
     rep(d,0,4){
          int x = dx[d] + i, y = dy[d] + j;
          if(x > 0 && x <= n && y > 0 && y <= m && !wall[x][y]) res.pb({1, {x, y}});
     }
     rep(d,0,4) if(ad[i][j][d].ff + 1) res.pb({dist_wall[i][j], ad[i][j][d]});
     return res;
}

void clc_portal_edge(){
     rep(i,0,n+2) rep(j,0,m+2) rep(d,0,4) ad[i][j][d] = {-1, -1};
     rep(i,0,n+2) rep(j,0,m+2) {
          if(wall[i][j]) rep(d,0,4){
               int x = i + dx[d], y = j + dy[d];
               int a = x, b = y;
               while(x > 0 && x <= n && y > 0 && y <= m && !wall[x][y]) ad[x][y][d] = {a, b}, x += dx[d], y += dy[d];
          }
     }
}

int dijkstra(){
     vector<vector<pp>> vc(n*m);
     vc[0].pb(st);
     vector<vector<int>> dist(n + 2, vector<int>(m + 2, inf)); dist[st.ff][st.ss] = 0;
     rep(i,0,sz(vc)){
          for(pp c: vc[i]){
               if(dist[c.ff][c.ss] - i) continue;
               if(c == en) return i;
               for(auto[w, p]: adj(c.ff, c.ss)) if(dist[p.ff][p.ss] > i + w)
                    vc[dist[p.ff][p.ss] = i + w].pb(p);
          }
     }
     return -1;
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     cin >> n >> m;
     rep(i,0,n+2) rep(j,0,m+2) wall[i][j] = true;
     rep(i,1,n+1) rep(j,1,m+1){
          char c; cin >> c;
          if(c == '#') continue;
          if(c == 'S') st = {i, j};
          else if(c == 'C') en = {i, j};
          wall[i][j] = false;
     }
     clc_bfs_wall();
     clc_portal_edge();
     cout << dijkstra() << '\n';
     return 0;
}

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