제출 #683266

#제출 시각아이디문제언어결과실행 시간메모리
683266ajstillpracticinMecho (IOI09_mecho)C++17
100 / 100
534 ms7692 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second int dx[4]{1,0,-1,0}; int dy[4]{0,1,0,-1}; char direc[4]{'R','U','L','D'}; void setIO(string filename=""){ ios_base::sync_with_stdio(0); cin.tie(0); if(filename.size()){ freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } } const int INF=(int) 1e9; const int M= 1e9+7; const ll MAXD = 1e18; // const int MAXN = 1e4; int main() { setIO(); int n,s; cin >> n >> s; string grid[n]; for(int i=0;i<n;++i) cin >> grid[i]; vector<pair<int,int>> hive; int mechox,mechoy,homex,homey; for(int i=0;i<n;++i) for(int j=0;j<n;++j){ if(grid[i][j]=='M'){ mechox=i; mechoy=j; } else if(grid[i][j]=='H'){ hive.push_back({i,j}); } else if(grid[i][j]=='D'){ homex=i; homey=j; } } int l=0; int r=n*n; while(l<=r){ bool bee_vis[n][n]{}; bool me_vis[n][n]{}; int bee_time[n][n]; int me_time[n][n]; memset(bee_time, 0 , sizeof(bee_time)); memset(me_time, 0 , sizeof(me_time)); int time=(l+r)/2; queue<pair<int,int>> q; for(auto i : hive){ q.push({i.fi,i.se}); bee_vis[i.fi][i.se]=1; } while(!q.empty()){ int x=q.front().fi; int y=q.front().se; q.pop(); for(int i=0;i<4;++i){ int nx=x+dx[i],ny=y+dy[i]; if(nx<0 || nx>=n || ny<0 || ny>=n) continue; if(!(grid[nx][ny]=='G' || grid[nx][ny]=='M') || bee_vis[nx][ny]) continue; bee_time[nx][ny]=bee_time[x][y]+1; q.push({nx,ny}); bee_vis[nx][ny]=1; } } q.push({mechox,mechoy}); me_vis[mechox][mechoy]=1; if(bee_time[mechox][mechoy]<=time) q.pop(); while(!q.empty()){ int x=q.front().fi; int y=q.front().se; q.pop(); for(int i=0;i<4;++i){ int nx=x+dx[i],ny=y+dy[i]; if(nx<0 || nx>=n || ny<0 || ny>=n) continue; if(!(grid[nx][ny]=='G' || grid[nx][ny]=='M') || me_vis[nx][ny]) continue; if((me_time[x][y]+1)/s < bee_time[nx][ny]-time){ me_vis[nx][ny]=1; q.push({nx,ny}); me_time[nx][ny]=me_time[x][y]+1; } } } bool ans=0; for(int i=0;i<4;++i){ int nx=homex+dx[i],ny=homey+dy[i]; if(nx<0 || nx>=n || ny<0 || ny>=n) continue; if((me_time[nx][ny]/s)<bee_time[nx][ny]-time && me_vis[nx][ny]){ ans=1; break; } } if(ans) l=time+1; else r=time-1; } cout << l-1 << "\n"; }

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

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen((filename + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:16:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   freopen((filename + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:94:29: warning: 'mechoy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |   if(bee_time[mechox][mechoy]<=time)
      |      ~~~~~~~~~~~~~~~~~~~~~~~^
mecho.cpp:94:29: warning: 'mechox' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:118:8: warning: 'homex' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |    int nx=homex+dx[i],ny=homey+dy[i];
      |        ^~
mecho.cpp:118:23: warning: 'homey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |    int nx=homex+dx[i],ny=homey+dy[i];
      |                       ^~
#Verdict Execution timeMemoryGrader output
Fetching results...