Submission #583973

#	Time	Username	Problem	Language	Result	Execution time	Memory
583973		Omar_Elgedawy	Mecho (IOI09_mecho)	C++14	6 / 100	306 ms	65536 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define cin(vec)        for(auto& i : vec) cin >> i
#define cout(vec)       for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast            ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b)     for (int i = a; i < b; i++)
#define F               first
#define S               second
#define pb(n)           push_back(n)
#define pf(n)           push_front(n)
#define dci(d)          fixed<<setprecision(d)
#define sp              ' '
#define el              '\n'
#define all(v)          v.begin(),v.end()
// #define int             long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=8e2+5,M=1e2+5,Mod=1e9;
char grid[N][N];
int block[N][N],vis[N][N],n,s,dp[N][N];
int valid(int i,int j){
  return (i>=0&&j>=0&&i<n&&j<n);
}
struct cell{
  int i;
  int j;
  int t;
};
queue<cell>q;
void bfs(){
  while(q.size()){
    int i=q.front().i;
    int j=q.front().j;
    int t=q.front().t;
    q.pop();
    vis[i][j]=1;
    block[i][j]=min(t,block[i][j]);
    for(int k=0;k<4;k++){
      int x=dx[k]+i;
      int y=dy[k]+j;
      if(valid(x,y)&&grid[x][y]=='G'&&!vis[x][y]){
        q.push({x,y,t+1});
      }
    }
  }
}
void bfs2(int i,int j){
  int t=0;
  q.push({i,j,t});
  dp[i][j]=0;
  while(q.size()){
    i=q.front().i;
    j=q.front().j;
    t=q.front().t;
    q.pop();
    if(grid[i][j]=='D')continue;
    for(int k=0;k<4;k++){
      int x=dx[k]+i;
      int y=dy[k]+j;
      if(valid(x,y)&&(grid[x][y]=='G'||grid[x][y]=='D')&&
         dp[x][y]>t+1&&block[x][y]>=(t+1)/s){
        q.push({x,y,t+1});
        dp[x][y]=t+1;
      }
    }
  }
}
bool bfs3(int i,int j,int st){
  queue<cell>cu;
  cu.push({i,j,st});
  memset(vis,0,sizeof vis);
  vis[i][j]=1;
  int t;
  while(cu.size()){
    i=cu.front().i;
    j=cu.front().j;
    t=cu.front().t;
    cu.pop();
    if(grid[i][j]=='D')return 1;
    for(int k=0;k<4;k++){
      int x=dx[k]+i;
      int y=dy[k]+j;
      if(valid(x,y)&&(grid[x][y]=='G'||grid[x][y]=='D')&&block[x][y]>=st+(t+1)/s&&!vis[x][y]){
        cu.push({x,y,t+1});
        vis[x][y]=1;
      }
    }
  }
  return 0;
}
void testcase(int h){
  cin>>n>>s;
  int xst,yst,xed,yed;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      block[i][j]=1e9;
      dp[i][j]=1e9;
    }
  }
  for(int i=0;i<n;i++){
    string s;cin>>s;
    for(int j=0;j<n;j++){
      grid[i][j]=s[j];
      if(s[j]=='T')
        block[i][j]=-1;
      if(s[j]=='H')
        q.push({i,j,0});
      if(s[j]=='M')xst=i,yst=j;
      if(s[j]=='D')xed=i,yed=j;
    }
  }
  memset(vis,0,sizeof vis);
  bfs();
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<n;j++){
  //     cout<<block[i][j]<<' ';
  //   }cout<<el;
  // }
  bfs2(xst,yst);
  int l=0,r=n*n+1;
  int mx=0;
  while(l<=r){
    int m=(l+r)/2;
    // cout<<l<<' '<<m<<' '<<r<<el;
    int x=bfs3(xst,yst,m);
    if(x){
      mx=m;
      l=m+1;
    }
    else{
      r=m-1;
    }
  }
  cout<<mx<<el;
}
int32_t main()
{
  // fast
  testcase(1);
  // int tc;cin>>tc;for(int i=1;i<=tc;i++)testcase(i);
  return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void testcase(int)':
mecho.cpp:93:15: warning: variable 'xed' set but not used [-Wunused-but-set-variable]
   93 |   int xst,yst,xed,yed;
      |               ^~~
mecho.cpp:93:19: warning: variable 'yed' set but not used [-Wunused-but-set-variable]
   93 |   int xst,yst,xed,yed;
      |                   ^~~
mecho.cpp:125:15: warning: 'yst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |     int x=bfs3(xst,yst,m);
      |           ~~~~^~~~~~~~~~~
mecho.cpp:125:15: warning: 'xst' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 6 / 100