제출 #554808

#제출 시각아이디문제언어결과실행 시간메모리
554808roctes7Mecho (IOI09_mecho)C++17
4 / 100
549 ms31744 KiB
#include<bits/stdc++.h> using namespace std; #define in insert #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl "\n" #define Endl "\n" #define ENDL "\n" #define fi first #define se second #define be begin() #define en end() #define pb push_back #define mpa make_pair typedef long long ll; typedef long double ld; const int MOD=1e9+7; const int MAX=2e5+1; ll n,s; string arr[802][802]; bool vist[802][802]; ll mechoDist[802][802]; ll BeesDist[802][802]; pair<ll,ll> mecho; pair<ll,ll> home; ll dx[]={1,-1,0,0}; ll dy[]={0,0,1,-1}; bool valid (ll x,ll y){ return x>=1&&x<=n&&y>=1&&y<=n&&!vist[x][y]&&arr[x][y]!="T"; } bool check =false; void bfs (ll val){ vist[mecho.fi][mecho.se]=true; queue<pair<ll,ll>>q; q.push(mecho); while (!q.empty()){ auto p =q.front(); ll x = p.fi; ll y = p.se; q.pop(); if(x==home.fi&&y==home.se)check=true; for (ll i=0;i<4;i++){ ll nx = x+dx[i]; ll ny = y+dy[i]; if(valid(nx,ny)&&arr[nx][ny]=="G"&&val+mechoDist[nx][ny]<BeesDist[nx][ny]){ vist[nx][ny]=true; q.push(mpa(nx,ny)); } } } } int main(){ fastio //freopen("11.in","r",stdin); //freopen("cl.out","w",stdout); cin>>n>>s; for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){ BeesDist[i][j]=1e9; mechoDist[i][j]=1e9; } for (ll i=1;i<=n;i++){ string s; cin>>s; for (ll j=1;j<=n;j++){ arr[i][j]=s[j-1]; if(arr[i][j]=="M")mecho=mpa(i,j); else if (arr[i][j]=="D")home = mpa(i,j); } } queue <pair<ll,ll>> q; q.push(mecho); mechoDist[mecho.fi][mecho.se]=0; vist[mecho.fi][mecho.se]=true; while(!q.empty()){ auto p = q.front(); ll x = p.fi; ll y = p.se; q.pop(); for (ll i=0;i<4;i++){ ll nx = x+dx[i]; ll ny = y+dy[i]; if(valid(nx,ny)&&arr[nx][ny]!="H"){ mechoDist[nx][ny]=mechoDist[x][y]+1; vist[nx][ny]=true; q.push(mpa(nx,ny)); } } } for (ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){ mechoDist[i][j]=mechoDist[i][j]/s; vist[i][j]=false; } for (ll i=1;i<=n;i++)for (ll j=1;j<=n;j++){ if(arr[i][j]=="H"){ q.push(mpa(i,j)); BeesDist[i][j]=0; vist[i][j]=true; } } while(!q.empty()){ auto p = q.front(); ll x = p.fi; ll y = p.se; q.pop(); for (ll i=0;i<4;i++){ ll nx = x+dx[i]; ll ny = y+dy[i]; if(valid(nx,ny)&&arr[nx][ny]!="D"&&arr[nx][ny]!="H"){ BeesDist[nx][ny]=BeesDist[x][y]+1; vist[nx][ny]=true; q.push(mpa(nx,ny)); } } } /*cout<<endl<<endl; for(ll i=1;i<=n;i++){for (ll j=1;j<=n;j++){ if(arr[i][j]=="G") cout<<mechoDist[i][j]; else cout<<arr[i][j]; } cout<<endl; } cout<<endl<<endl; for(ll i=1;i<=n;i++){for (ll j=1;j<=n;j++){ cout<<BeesDist[i][j]; } cout<<endl; }*/ ll l=0; ll r = 1e9; ll ans =-1; while (l<=r){ ll mid = (l+r)/2; for (ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){ vist[i][j]=false; } check=false; bfs(mid); if(check){ l=mid+1; ans = mid; } else { r=mid-1; } } cout<<ans; return 0; } unsigned long long power(unsigned long long x, ll y, ll p) { unsigned long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } unsigned long long modInverse(unsigned long long n, ll p) { return power(n, p - 2, p); }
#Verdict Execution timeMemoryGrader output
Fetching results...