Submission #1144038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144038		sitingfake	Mecho (IOI09_mecho)	C++20	98 / 100	171 ms	6168 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1)
#define flip(x,i) (x^(1<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define sitingfake 1
#define orz 1
const int mod=1e9+7;
const long long linf=4557430888798830399;
const int inf=1061109567;
const int maxarr=1e6+5;
const double pi=acos(-1);
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};
const int maxn=801;
int n,S;
int distH[maxn][maxn],distM[maxn][maxn];
char a[maxn][maxn];
ii st,fin;
int ans=-1;
void bfs1()
{
    queue<ii>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]=='H')
            {
                distH[i][j]=0;
                q.push(ii(i,j));
            }
            else distH[i][j]=inf;
        }
    }
    while(!q.empty())
    {
        int u=q.front().fi;
        int v=q.front().se;
        q.pop();
        for(int z=0;z<4;z++)
        {
            int i=dx[z]+u;
            int j=dy[z]+v;
            if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]!='T'&&a[i][j]!='D')
            {
                if(distH[i][j]>distH[u][v]+1)
                {
                    distH[i][j]=distH[u][v]+1;
                    q.push(ii(i,j));
                }
            }
        }
    }
}
bool check(int x)
{
    if(distH[st.fi][st.se]<=x) return 0;
    queue<ii>q;
    vector<vector<int>>distM(n+5,vector<int>(n+5,inf));
    q.push(st);
    distM[st.fi][st.se]=0;
    while(!q.empty())
    {
        int u=q.front().fi;
        int v=q.front().se;
        q.pop();
        for(int z=0;z<4;z++)
        {
            int i=dx[z]+u;
            int j=dy[z]+v;
            if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]!='T')
            {
                int val=distM[u][v]+1;
                if(((val/S)+x)<distH[i][j]&&distM[i][j]>val)
                {
                    distM[i][j]=distM[u][v]+1;
                    q.push(ii(i,j));
                }
            }
        }
    }
    for(int z=0;z<4;z++)
    {
        int i=dx[z]+fin.fi;
        int j=dy[z]+fin.se;
        if(i>=1&&i<=n&&j>=1&&j<=n&&a[i][j]!='T')
        {
            int val=distM[i][j]/S;
            if(val+x<distH[i][j]) return 1;
        }
    }
    return 0;
}
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   cin>>n>>S;
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
           cin>>a[i][j];
           if(a[i][j]=='M') st=ii(i,j);
           else if(a[i][j]=='D')fin=ii(i,j);
       }
   }
   bfs1();
   int l=0,r=n*n;
   while(l<=r)
   {
       int mid=(r+l)>>1;
       if(check(mid))
       {
           ans=mid;
           l=mid+1;
       }
       else r=mid-1;
   }
   cout<<ans;
   //execute;
}
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT
*/

• Subtask 1: 98 / 100