제출 #743004

#제출 시각아이디문제언어결과실행 시간메모리
743004Dan4Life포탈들 (BOI14_portals)C++17
100 / 100
373 ms43040 KiB
#include <bits/stdc++.h> using namespace std; #define sz(a) (int)a.size() const int N = (int)1e3+10; using ar = array<int,3>; int X[] = {1,-1,0,0}; int Y[] = {0,0,1,-1}; string a[N]; bool vis[N][N]; int n, m, stX, stY, enX, enY; pair<int,int> dr[4][N][N]; int D[N][N], sh[N][N]; priority_queue<ar,vector<ar>,greater<ar>> pq; __attribute__((always_inline)) bool valid(int i, int j){ return i>=0 and j>=0 and i<n and j<m and a[i][j]!='#'; } void dijkstra(int sti, int stj){ memset(D,63,sizeof(D)); pq.push({0,sti,stj}); D[sti][stj] = 0; while(!pq.empty()){ auto [w,i,j] = pq.top(); pq.pop(); if(vis[i][j]) continue; vis[i][j]=1; for(int k = 0; k < 4; k++){ auto [ni,nj] = dr[k][i][j]; if(valid(ni,nj) and D[ni][nj]>D[i][j]+sh[i][j]) D[ni][nj] = D[i][j]+sh[i][j], pq.push({D[ni][nj],ni,nj}); ni = i+X[k], nj = j+Y[k]; if(valid(ni,nj) and D[ni][nj]>D[i][j]+1) D[ni][nj] = D[i][j]+1, pq.push({D[ni][nj],ni,nj}); } } } int32_t main(){ cin >> n >> m; memset(sh,63,sizeof(sh)); for(int i = 0; i < n; i++){ cin >> a[i]; for(int j = 0; j < m; j++){ if(a[i][j]=='C') enX=i,enY=j; else if(a[i][j]=='S') stX=i,stY=j; } int last = 0; for(int j = 0; j < m; j++){ if(a[i][j]=='#') last = j+1; else{ dr[0][i][j]={i,last}; sh[i][j]=min(sh[i][j],abs(last-j)+1); } } last = m-1; for(int j = m-1; j >= 0; j--){ if(a[i][j]=='#') last = j-1; else{ dr[1][i][j]={i,last}; sh[i][j]=min(sh[i][j],abs(last-j)+1); } } } for(int j = 0; j < m; j++){ int last = 0; for(int i = 0; i < n; i++){ if(a[i][j]=='#') last = i+1; else{ dr[2][i][j]={last,j}; sh[i][j]=min(sh[i][j],abs(last-i)+1); } } last = n-1; for(int i = n-1; i >= 0; i--){ if(a[i][j]=='#') last = i-1; else{ dr[3][i][j]={last,j}; sh[i][j]=min(sh[i][j],abs(last-i)+1); } } } dijkstra(stX,stY); cout << D[enX][enY]; }

컴파일 시 표준 에러 (stderr) 메시지

portals.cpp: In function 'void dijkstra(int, int)':
portals.cpp:25:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   25 |   if(vis[i][j]) continue; vis[i][j]=1;
      |   ^~
portals.cpp:25:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   25 |   if(vis[i][j]) continue; vis[i][j]=1;
      |                           ^~~
portals.cpp: At global scope:
portals.cpp:16:37: warning: 'always_inline' function might not be inlinable [-Wattributes]
   16 | __attribute__((always_inline)) bool valid(int i, int j){
      |                                     ^~~~~
#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...