Submission #1162298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162298		escobrand	Mecho (IOI09_mecho)	C++20	84 / 100	134 ms	11336 KiB

mecho

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb emplace_back
#define ll long long 
#define fi first
#define se second
int t,n,i,m,j,x,y,X,Y;
const int maxn= 8e2 + 10;
int di[4] = {1,0,-1,0},dj[4] = {0,1,0,-1};
char ch[maxn][maxn];
pair<int,int> b[maxn][maxn],bb[maxn][maxn];
queue<pair<int,int>> q;

bool check(int i,int j)
{
  return i >= 0 && j >= 0 && i < n && j < n;
}

pair<int,int> cal(pair<int,int> tmp)
{
  tmp.se++;
  tmp.fi += tmp.se/m;
  tmp.se %= m;
  return tmp;
}

bool solve(int tmp)
{
  for(i = 0;i<n;i++)
    {
      for(j = 0;j<n;j++)
      {
        bb[i][j] = b[i][j];
      }
    }
  queue<pair<int,int>> q;
  q.push({x,y});
  bb[x][y] = {tmp,0};
  while(q.size())
  {
    i = q.front().fi;
    j = q.front().se;
    q.pop();
    for(int k = 0;k<4;k++)
    {
      int I = i + di[k],J = j + dj[k];
      if(check(I,J) && bb[I][J] > cal(bb[i][j]))
      {
        bb[I][J] = cal(bb[i][j]);
        q.push({I,J});
      }
    }
  }
  return bb[X][Y].fi != 1e9;
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    for(i = 0;i<n;i++)
    {
      for(j = 0;j<n;j++)
      {
        cin>>ch[i][j];
        if(ch[i][j] == 'H')q.push({i,j});
        if(ch[i][j] == 'M')
        {
          x = i,y = j;
        }
        if(ch[i][j] == 'D')
        {
          X = i,Y = j;
        }
        if(ch[i][j] == 'T' || ch[i][j] == 'H')
        {
          if(ch[i][j] == 'T')b[i][j].fi = -1e9;
        }
        else b[i][j].fi = 1e9;
      }
    }
    
    while(q.size())
    {
      i = q.front().fi;
      j = q.front().se;
      q.pop();
      for(int k = 0;k<4;k++)
      {
        int I = i + di[k],J = j + dj[k];
        if(check(I,J) && ch[I][J] != 'M' && ch[I][J] != 'D' && b[I][J].fi > b[i][j].fi +1)
        {
          b[I][J].fi = b[i][j].fi +1;
          q.push({I,J});
        }
      }
    }
    int l = -1,r = 5e6,mid;
    while(l < r)
    {
      mid = (l + r + 1)/2;
      if(solve(mid))l = mid;
      else r = mid - 1;
    }
    cout<<l;
    
    return 0;
}

• Subtask 1: 84 / 100