제출 #554808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554808		roctes7	Mecho (IOI09_mecho)	C++17	4 / 100	549 ms	31744 KiB

mecho

#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);
}

• Subtask 1: 4 / 100