Submission #1169364

#TimeUsernameProblemLanguageResultExecution timeMemory
1169364I_FloPPed21Mecho (IOI09_mecho)C++20
48 / 100
139 ms105892 KiB
#include <iostream> #include <queue> using namespace std; const int N=805; int n,m; char mat[N][N]; int dx[]= {1,0,-1,0}; int dy[]= {0,-1,0,1}; bool inmat(int i,int j) { return(i>=1&&i<=n&&j>=1&&j<=n); } struct mecho { int x,y,val,rem; } q[N*N*10]; bool viz[N][N]; int timp[N][N]; void citeste() { cin>>n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) cin>>mat[i][j]; } } void do_bees() { int siz=0; int point=1; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { timp[i][j]=1e9+3; if(mat[i][j]=='H') { timp[i][j]=0; viz[i][j]=true; siz++; q[siz]= {i,j,0,0}; } } } while(point<=siz) { int x=q[point].x; int y=q[point].y; point++; for(int i=0; i<4; i++) { int a=x+dx[i]; int b=y+dy[i]; if(!inmat(a,b)) continue; if(mat[a][b]=='T'||mat[a][b]=='D') continue; if(viz[a][b]==false||timp[a][b]>timp[x][y]) { viz[a][b]=true; timp[a][b]=timp[x][y]+1; siz++; q[siz]={a,b,0,0}; } } } } int ans=-1; bool check(int val) { int siz=0; int point=1; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { viz[i][j]=false; if(mat[i][j]=='M') { viz[i][j]=true; siz++; q[siz]={i,j,val,m-1}; } } } while(point<=siz) { int x=q[point].x; int y=q[point].y; int val=q[point].val; if(timp[x][y]<=val) { viz[x][y]=false; break; } int cate=q[point].rem; point++; if(cate==0) { val++; cate=m; } cate--; for(int i=0; i<4; i++) { int a=x+dx[i]; int b=y+dy[i]; if(!inmat(a,b)) continue; if(mat[a][b]=='T') continue; if(timp[a][b]>val&&viz[a][b]==false) { viz[a][b]=true; siz++; q[siz]={a,b,val,cate}; } } } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(mat[i][j]=='D') if(viz[i][j]==true) return true; return false; } void bin_search() { int st=0,dr=n*n; while(st<=dr) { int mij=(st+dr)/2; if(check(mij)) { ans=mij; st=mij+1; } else { dr=mij-1; } } cout<<ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); citeste(); do_bees(); bin_search(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...