Submission #1230318

#TimeUsernameProblemLanguageResultExecution timeMemory
1230318lukasuliashviliMecho (IOI09_mecho)C++20
84 / 100
319 ms62120 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define fs first #define sc second #define pb push_back const int N=805; char a[N][N],g[N*N]; vector<int> v[N*N]; int fix[N*N],t[N*N],n,s,fix2[N*N],t2[N*N],st,en; int check(int mid ){ for(int i=1; i<=n*n; i++){ t2[i]=1e9; fix[i]=0; } deque<int> deq; deq.pb(st); fix[st]=1; t2[st]=mid; while(!deq.empty()){ int to=deq.front(); deq.pop_front(); for(int i=0; i<v[to].size(); i++){ int to1=v[to][i]; if(g[to1]=='D'){ return 1; } if(fix[to1]==1 or t[to1]<=min(t2[to1],t2[to]+1)){ continue; } t2[to1]=min(t2[to1],t2[to]+1); deq.pb(to1); fix[to1]=1; } } // for(int i=1; i<=n; i++){ // for(int j=1; j<=n; j++){ // cout<<t2[(i-1)*n+j]<<" "; // } // cout<<endl; // } return -1; } void bfs (){ deque<int> deq; for(int i=1; i<=n*n; i++){ if(g[i]=='H'){ deq.pb(i); fix[i]=1; t[i]=0; } } while(!deq.empty()){ int to=deq.front(); deq.pop_front(); for(int i=0; i<v[to].size(); i++){ int to1=v[to][i]; if(fix[to1]==1){ continue; } t[to1]=min(t[to1],t[to]+s); deq.pb(to1); fix[to1]=1; } } } signed main(){ cin>>n>>s; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ cin>>a[i][j]; g[(i-1)*n+j]=a[i][j]; } } for(int i=1; i<=n*n; i++){ t[i]=1e9; t2[i]=1e9; if(g[i]=='M'){ st=i; } if(g[i]=='D'){ en=i; } } for(int i=1; i<=n*n; i++){ if(g[i]=='T')continue; if(i+1>=1 and i+1<=n*n){ if(g[i]!='T' and g[i+1]!='T' and i%n!=0){ v[i].pb(i+1); v[i+1].pb(i); } } if(i+n<=n*n and i+n>=1 ){ if(g[i+n]!='T' and g[i]!='T'){ v[i].pb(i+n); v[i+n].pb(i); } } } bfs(); if(check(0)==-1){ cout<<-1<<endl; return 0; } int l=0; int r=n*n; int ans=0; // for(int i=1; i<=n; i++){ // for(int j=1; j<=n; j++){ // cout<<t[(i-1)*n+j]<<" "; // } // cout<<endl; // } while(l<=r){ int mid=(l+r)/2; if(check(mid*s)!=-1){ l=mid+1; ans=max(mid,ans); } else{ r=mid-1; } } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...