Submission #394768

#TimeUsernameProblemLanguageResultExecution timeMemory
394768negar_aPortals (BOI14_portals)C++14
100 / 100
749 ms175600 KiB
//!yrt tsuj uoy srettam gnihton no emoc #include <bits/stdc++.h> //#pragma GCC target ("avx2") #pragma GCC optimization ("Ofast") #pragma GCC optimization ("unroll-loops") using namespace std; typedef long long ll; typedef long double ld; #define um unordered_map #define pb push_back #define mp make_pair #define pii pair <int, int> #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define F first #define S second int r, c; const int N = 1e3 + 2; pii up[N][N], dw[N][N], le[N][N], ri[N][N]; int mn[N][N], inf = 1e9 + 7; char s[N][N]; vector <pair <pii, int>> adj[N][N]; int h[N][N]; bool mark[N][N]; set <pair <int, pii>> q; inline void add_edge(int i, int j){ adj[i][j].pb({dw[i][j], mn[i][j] + 1}); adj[i][j].pb({le[i][j], mn[i][j] + 1}); adj[i][j].pb({ri[i][j], mn[i][j] + 1}); adj[i][j].pb({up[i][j], mn[i][j] + 1}); } inline void UP(){ for(int i = 0; i < r; i ++){ for(int j = 0; j < c; j ++){ if(i <= 0 || s[i - 1][j] == '#'){ up[i][j] = {i, j}; }else{ up[i][j] = up[i - 1][j]; } mn[i][j] = min(mn[i][j], abs(i - up[i][j].F)); } } } inline void DOWN(){ for(int i = r - 1; i >= 0; i --){ for(int j = 0; j < c; j ++){ if(i >= r - 1 || s[i + 1][j] == '#'){ dw[i][j] = {i, j}; }else{ dw[i][j] = dw[i + 1][j]; } mn[i][j] = min(mn[i][j], abs(i - dw[i][j].F)); } } } inline void LEFT(){ for(int j = 0; j < c; j ++){ for(int i = 0; i < r; i ++){ if(j <= 0 || s[i][j - 1] == '#'){ le[i][j] = {i, j}; }else{ le[i][j] = le[i][j - 1]; } mn[i][j] = min(mn[i][j], abs(j - le[i][j].S)); } } } inline void RIGHT(){ for(int j = c - 1; j >= 0; j --){ for(int i = 0; i < r; i ++){ if(j >= c - 1 || s[i][j + 1] == '#'){ ri[i][j] = {i, j}; }else{ ri[i][j] = ri[i][j + 1]; } mn[i][j] = min(mn[i][j], abs(j - ri[i][j].S)); } } } inline void dijk(pii v){ q.insert({0, v}); h[v.F][v.S] = 0; // mark[v.F][v.S] = true; while(q.size()){ int w = q.begin() -> F; pii x = q.begin() -> S; q.erase(q.begin()); // mark[x.F][x.S] = false; if(w <= h[x.F][x.S]){ for(auto u : adj[x.F][x.S]){ if(h[u.F.F][u.F.S] > h[x.F][x.S] + u.S){ h[u.F.F][u.F.S] = h[x.F][x.S] + u.S; // if(!mark[u.F.F][u.F.S]){ // mark[u.F.F][u.F.S] = true; q.insert({h[u.F.F][u.F.S], u.F}); // } } } } } } int main(){ fast_io; scanf("%d %d", &r, &c); pii st, en; for(int i = 0; i < r; i ++){ scanf("%s", &s[i]); for(int j = 0; j < c; j ++){ if(s[i][j] == 'S'){ st = {i, j}; } if(s[i][j] == 'C'){ en = {i, j}; } mn[i][j] = h[i][j] = inf; } } UP(); DOWN(); LEFT(); RIGHT(); for(int i = 0; i < r; i ++){ for(int j = 0; j < c; j ++){ if(i > 0 && s[i - 1][j] != '#'){ adj[i][j].pb({{i - 1, j}, 1}); } if(i < r - 1 && s[i + 1][j] != '#'){ adj[i][j].pb({{i + 1, j}, 1}); } if(j > 0 && s[i][j - 1] != '#'){ adj[i][j].pb({{i, j - 1}, 1}); } if(j < c - 1 && s[i][j + 1] != '#'){ adj[i][j].pb({{i, j + 1}, 1}); } add_edge(i, j); } } dijk(st); printf("%d", h[en.F][en.S]); return 0; }

Compilation message (stderr)

portals.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("Ofast")
      | 
portals.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
portals.cpp: In function 'int main()':
portals.cpp:112:11: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1002]' [-Wformat=]
  112 |   scanf("%s", &s[i]);
      |          ~^   ~~~~~
      |           |   |
      |           |   char (*)[1002]
      |           char*
portals.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |  scanf("%d %d", &r, &c);
      |  ~~~~~^~~~~~~~~~~~~~~~~
portals.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |   scanf("%s", &s[i]);
      |   ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...