Submission #1037042

#TimeUsernameProblemLanguageResultExecution timeMemory
1037042hippo123Mecho (IOI09_mecho)C++17
64 / 100
146 ms7252 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second #define pr pair<int, int> #define pb push_back const int ndim=800; const int dmax=1e9; vector<string> mp(ndim); vector<int> level(ndim*ndim, -1); vector<int> level2(ndim*ndim, -1); int dx[4]={1, -1, 0, 0}; int dy[4]={0, 0, 1, -1}; int n, s; bool dmcheck(int x, int y){ if(x>=0 && x<n && y>=0 && y<n && mp[x][y]!='T' && mp[x][y]!='D' && level[x*n+y]==-1 ) return true; else return false; } bool bearcheck(int x, int y){ if(x>=0 && x<n && y>=0 && y<n && mp[x][y]!='T' && mp[x][y]!='H' && level2[x*n+y]==-1 ) return true; else return false; } bool check(int mid, pr M, pr hs){ for (int i=0; i<n*n; i++) level2[i]=-1; queue<pr> q; q.push({M.f*n+M.s, 0}); level2[M.f*n+M.s]=0; bool judge=false; while(!q.empty()){ pr n1=q.front(); q.pop(); int nd=n1.f; int lev=n1.s; int x=nd/n; int y=nd%n; //cout<< "x/y= "<<x<<" "<<y<<endl; //cout<<" level[x*n+y]-mid= "<<level[x*n+y]-mid<<endl; if(lev>=(level[x*n+y]-mid)*s) continue; for (int i=0; i<4; i++){ int x2=x+dx[i]; int y2=y+dy[i]; if( bearcheck(x2, y2)){ //cout<<" x2/y2= "<<x2<<" "<<y2<< "hs= "<<hs.f<<" "<<hs.s<<endl; if(x2==hs.f && y2==hs.s ){ judge=true; break;} //cout<<" lev+1 / (level[x2*n+y2]-mid)*s= "<<lev+1 <<" "<< (level[x2*n+y2]-mid)*s<<endl; if(lev+1 <= (level[x2*n+y2]-mid)*s){ // level is bee q.push({x2*n+y2, lev+1}); level2[x2*n+y2]= lev+1; } } if(judge) break; } if(judge) break; } //for (int i=0; i<n; i++){ // for (int j=0; j<n; j++) cout<<level2[i*n+j]<<" "; // cout<<endl; //} //cout<<" judge= "<<judge<<endl; return judge; } int main(){ cin>>n>>s; vector<pr> hv; pr M, hs; for (int i=0; i<n; i++) { cin>>mp[i]; for (int j=0; j<n; j++){ if(mp[i][j]=='H') hv.pb({i, j}); if(mp[i][j]=='M') M={i, j}; if(mp[i][j]=='D') hs={i, j}; } } //cout<<" hs= "<<hs.f<<" "<<hs.s<<endl; queue<pr> q; for (auto elem: hv) { q.push({elem.f*n+elem.s, 0}); level[elem.f*n+elem.s]=0; } while (!q.empty()){ pr n1=q.front(); q.pop(); int nd=n1.f; int lev=n1.s; int x=nd/n; int y=nd%n; for (int i=0; i<4; i++){ int x2=x+dx[i]; int y2=y+dy[i]; if(dmcheck(x2, y2)){ q.push({x2*n+y2, lev+1}); level[x2*n+y2]=lev+1; } } } //for (int i=0; i<n; i++){ // for (int j=0; j<n; j++) cout<<level[i*n+j]<<" "; // cout<<endl; //} int lft=0; int rht=100000; while(lft<rht ){ int mid=(rht+lft+1)/2; // cout<<" lft/rht/mid= "<<lft<<" "<<rht<<" "<<mid<<endl; if(check(mid, M, hs)) lft=mid; else rht=mid-1; } cout<<lft<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...