Submission #885751

#TimeUsernameProblemLanguageResultExecution timeMemory
885751nnhzzzPortals (BOI14_portals)C++14
100 / 100
158 ms47204 KiB
/* [Author: Nguyen Ngoc Hung] - From THPT Ngo Gia Tu with Love */ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <locale> #include <map> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <unordered_set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <valarray> #include <vector> #include <cstring> #include <unordered_map> #include <cmath> #include <array> #include <cassert> #include <random> #include <chrono> using namespace std; #define __nnhzzz__ signed main() #define BIT(i,j) ((i>>j)&1LL) #define MASK(i) (1LL<<i) #define ALL(x) (x).begin(),(x).end() #define SZ(x) (int)(x).size() #define _PB push_back #define fi first #define se second #define ll long long #define ld long double #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define pii pair<int,int> #define vpii vector<pii> #define vvpii vector<vpii> #define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j) #define REPD(i,be,en) for(int i = (be); i>=(en); i--) #define REP(i,be,en) for(int i = (be); i<=(en); i++) #define endl "\n" #define MP make_pair // #define int ll //-----------------------------------------------------------------------------------------------// int readInt(){ char c; do{ c = getchar(); }while(c!='-' && !isdigit(c)); bool neg = (c=='-'); int res = neg?0:c-'0'; while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0'); return neg?-res:res; } //------------------------------------------------------------------------------------------------// const ll LINF = 1e18; const int INF = 1e9; const int LOG = 20; const int MAXN = 1e3+3; const int N = 1e2+3; const int MOD = 1e9+7; const int BASE = 1e5; const ld EPS = 1e-9; const ld PI = acos(-1); const int OFFSET = 1e3; const int dx[] = {-1,0,1,0}; const int dy[] = {0,-1,0,1}; //------------------------------------------------------------------------------------------------// template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;} template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;} template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; } template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; } //------------------------------------------------------------------------------------------------// /* ---------------------------------------------------------------- END OF TEMPLATE ---------------------------------------------------------------- Nguyen Ngoc Hung - nnhzzz Training for VOI24 gold medal ---------------------------------------------------------------- */ struct Node{ int w,u,v; bool operator < (const Node &other) const { return w>other.w; } }; int dis_wall[MAXN][MAXN],f[MAXN][MAXN]; pii nxt[MAXN][MAXN][4]; char c[MAXN][MAXN]; pii S,T; int n,m; void solve(){ cin >> n >> m; REP(i,0,n+1) REP(j,0,m+1){ c[i][j] = '#'; f[i][j] = dis_wall[i][j] = INF; } queue<pii> q; REP(i,1,n){ REP(j,1,m){ cin >> c[i][j]; if(c[i][j]=='S') S.fi = i,S.se = j; if(c[i][j]=='C') T.fi = i,T.se = j; } } REP(i,0,n+1) REP(j,0,m+1){ if(c[i][j]=='#'){ dis_wall[i][j] = 0; q.push(MP(i,j)); } } REP(i,1,n){ REP(j,1,m){ if(c[i-1][j]=='#') nxt[i][j][2] = MP(i,j); else nxt[i][j][2] = nxt[i-1][j][2]; if(c[i][j-1]=='#') nxt[i][j][3] = MP(i,j); else nxt[i][j][3] = nxt[i][j-1][3]; } } REPD(i,n,1){ REPD(j,m,1){ if(c[i+1][j]=='#') nxt[i][j][0] = MP(i,j); else nxt[i][j][0] = nxt[i+1][j][0]; if(c[i][j+1]=='#') nxt[i][j][1] = MP(i,j); else nxt[i][j][1] = nxt[i][j+1][1]; } } while(SZ(q)!=0){ int x = q.front().fi,y = q.front().se; q.pop(); REP(i,0,3){ int nx = x+dx[i],ny = y+dy[i]; if(nx<0 || ny<0 || nx>n+1 || ny>m+1 || dis_wall[nx][ny]!=INF) continue; dis_wall[nx][ny] = dis_wall[x][y]+1; q.push(MP(nx,ny)); } } priority_queue<Node> heap; heap.push({0,S.fi,S.se}); f[S.fi][S.se] = 0; while(SZ(heap)!=0){ Node val = heap.top(); heap.pop(); int x = val.u,y = val.v,w = val.w; if(f[x][y]!=w) continue; REP(i,0,3){ int nx = x+dx[i],ny = y+dy[i]; if(c[nx][ny]!='#' && mini(f[nx][ny],f[x][y]+1)) heap.push({f[nx][ny],nx,ny}); nx = nxt[x][y][i].fi; ny = nxt[x][y][i].se; if(mini(f[nx][ny],f[x][y]+dis_wall[x][y])) heap.push({f[nx][ny],nx,ny}); } } cout << f[T.fi][T.se]; } __nnhzzz__{ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "test" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } #define task1 "nnhzzz" if(fopen(task1".inp","r")){ freopen(task1".inp","r",stdin); freopen(task1".out","w",stdout); } int test = 1; while(test--){ solve(); } cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n"; return 0; } /** /\_/\ * (= ._.) * / >TL \>AC **/

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
portals.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
portals.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
portals.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...