Submission #585098

#	Time	Username	Problem	Language	Result	Execution time	Memory
585098		MohammadAghil	Portals (BOI14_portals)	C++17	0 / 100	3 ms	596 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);
     #ifndef ONLINE_JUDGE
          freopen("in.in", "r", stdin);
          freopen("out.out", "w", stdout);
     #endif
     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;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:81:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |           freopen("in.in", "r", stdin);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
portals.cpp:82:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |           freopen("out.out", "w", stdout);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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