Submission #892982

#TimeUsernameProblemLanguageResultExecution timeMemory
892982ilefMecho (IOI09_mecho)C++14
100 / 100
156 ms7600 KiB
#include<bits/stdc++.h> using namespace std; int n,s; bool safe(int i,int j){ return i>=0 && i<n && j>=0 && j<n; } int di[4]={0,0,-1,1}; int dj[4]={1,-1,0,0}; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>s; char mat[n][n]; int dist1[n][n]; int dist2[n][n]; int homex,homey; int honx,hony; queue<pair<int,int>>q; bool vis1[n][n]; bool vis2[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ vis1[i][j]=false; vis2[i][j]=false; dist1[i][j]=0; dist2[i][j]=0; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>mat[i][j]; if(mat[i][j]=='M'){ honx=i; hony=j; } if(mat[i][j]=='D'){ homex=i; homey=j; } if(mat[i][j]=='H'){ q.push({i,j}); dist1[i][j]=0; vis1[i][j]=true; } } } while(!q.empty()){ const auto &[i,j]=q.front(); q.pop(); for(int l=0;l<4;l++){ int x=i+di[l]; int y=j+dj[l]; if(safe(x,y) && !vis1[x][y] && (mat[x][y]=='G'||mat[x][y]=='M')){ dist1[x][y]=dist1[i][j]+1; vis1[x][y]=true; q.push({x,y}); } } } //bool reached=false; int ll=0,rr=n*n; int ans=-1; while(ll<=rr){ int mid=(ll+rr)/2; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ vis2[i][j]=false; dist2[i][j]=0; } } if(mid<dist1[honx][hony]){ dist2[honx][hony]=0; vis2[honx][hony]=true; q.push({honx,hony}); } while(!q.empty()){ const auto &[i,j]=q.front(); q.pop(); for(int l=0;l<4;l++){ int x=i+di[l]; int y=j+dj[l]; if(safe(x,y) && (mat[x][y]=='G'|| mat[x][y]=='M')&& !vis2[x][y] &&((dist2[i][j]+1)/s<(dist1[x][y]-mid))){ dist2[x][y]=dist2[i][j]+1; vis2[x][y]=true; q.push({x,y}); } } } bool reached=false; for(int i=0;i<4;i++){ int x=homex+di[i]; int y=homey+dj[i]; if(safe(x,y) && vis2[x][y] && (mat[x][y]=='G'|| mat[x][y]=='M') && dist2[x][y]/s<dist1[x][y]-mid){ reached=true; } } if(reached){ ans=mid; ll=mid+1; } else{ //ans=mid; rr=mid-1; } } cout<<ans<<'\n'; }

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:50:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |         const auto &[i,j]=q.front();
      |                     ^
mecho.cpp:81:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         const auto &[i,j]=q.front();
      |                     ^
mecho.cpp:76:30: warning: 'hony' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             dist2[honx][hony]=0;
      |             ~~~~~~~~~~~~~~~~~^~
mecho.cpp:97:13: warning: 'homey' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |         int y=homey+dj[i];
      |             ^
mecho.cpp:76:30: warning: 'honx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             dist2[honx][hony]=0;
      |             ~~~~~~~~~~~~~~~~~^~
mecho.cpp:96:13: warning: 'homex' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |         int x=homex+di[i];
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...