Submission #892978

#TimeUsernameProblemLanguageResultExecution timeMemory
892978ilefMecho (IOI09_mecho)C++14
95 / 100
180 ms25688 KiB
#include<bits/stdc++.h> #define int long long using namespace std; const int inf=INT_MAX; 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]=inf; dist2[i][j]=inf; } } 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]=inf; } } 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<<ll-1<<endl; }

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:52:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         const auto &[i,j]=q.front();
      |                     ^
mecho.cpp:83:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |         const auto &[i,j]=q.front();
      |                     ^
mecho.cpp:66:9: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   66 |     int ans=-1;
      |         ^~~
mecho.cpp:78:30: warning: 'hony' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |             dist2[honx][hony]=0;
      |             ~~~~~~~~~~~~~~~~~^~
mecho.cpp:99:13: warning: 'homey' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |         int y=homey+dj[i];
      |             ^
mecho.cpp:98:13: warning: 'homex' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |         int x=homex+di[i];
      |             ^
mecho.cpp:78:30: warning: 'honx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |             dist2[honx][hony]=0;
      |             ~~~~~~~~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...