Submission #711256

#	Time	Username	Problem	Language	Result	Execution time	Memory
711256		Narka	Mecho (IOI09_mecho)	C++14	0 / 100	229 ms	65536 KiB

mecho

#include<bits/stdc++.h>
using namespace std ;
# define F first
# define S second
# define int long long
# define in insert
# define pb push_back
# define pob pop_back
# define INF INT_MAX
# define INFL 1e18 + 10 
# define mod 1000000007
# define vi vector<int>
# define pii pair<int , int>
# define vvi vector< vector<int> >
# define vpi vector<pair<int, int>> 
# define all(v) v.begin() , v.end()
# define debug(x) cerr << '\n' << #x << " = " << x << '\n' ;
# define rep( i , s , e ) for( int i = s ; i <= e ; i++ )
# define repR( i , e , s ) for( int i = e ; i >= s ; i-- )
# define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# define endl "\n"
vvi mp(805, vi(805)), mp1(805, vi(805));
vector<array<int, 2>> hives;
array<int, 2> st, nd;
int n, s;

bool safe(int i, int j){
  if(mp[i][j] == -2) return false;
  if(j < n && j >= 0 && i < n && i >= 0) return true;
  return false; 
}
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void attack(){
  queue<array<int, 2>> q;
  for(auto x : hives){
    q.push(x);
  }
  while(!q.empty()){
    array<int, 2> t = q.front(); q.pop();
    rep(i, 0, 3){
      int x = t[0] + dx[i];
      int y = t[1] + dy[i];
      if(safe(x, y)){
        if(mp[x][y] == 0) mp[x][y] = mp[t[0]][t[1]] + 1, q.push({x, y});
      } 
    }
  }
}

bool is_can(int v){
  queue<array<int, 2>> q, tmp; 
  q.push(st);
  if(mp[st[0]][st[1]] <= v) return false;
  int t = 0, b = 1;
  mp[st[0]][st[1]] = -2;
  while(!q.empty()){
    // if(v == 2){
    //   cout << "hi" <<endl;
    //   rep(i, 0, n-1){
    //     rep(j, 0, n-1){
    //       cout << mp[i][j] << " ";
    //     }
    //     cout << endl;
    //   }
    // }
    array<int, 2> tt = q.front(); q.pop();  
    rep(i, 0, 3){
     int x = tt[0] + dx[i];
     int y = tt[1] + dy[i];
     if(x == nd[0] && y == nd[1]) return true;
     if(safe(x, y) && b + v < mp[x][y]){
      tmp.push({x, y});
     } 
    }
    if(q.empty()){
      while(!tmp.empty()){
        tt = tmp.front();
        mp[tt[0]][tt[1]] = -2;
        q.push(tmp.front()); tmp.pop();
      }
      t++;
      if(t == s) t = 0, b++;
    }
  }
  return false;
}

void solve(){
  cin >> n >> s;
  rep(i, 0, n-1){
    string a;
    cin >> a;
    rep(j, 0, n-1){
      if(a[j] == 'T') mp[i][j] = -2;
      else if(a[j] == 'M') st = {i, j};
      else if(a[j] == 'H') mp[i][j] = 1, hives.pb({i, j});
      else if(a[j] == 'D') nd = {i, j};
    }
  }
  attack();
  mp1 = mp;
  int l = 0, r = mp[st[0]][st[1]] + 1, res = 0;
  while(l <= r){
    int md = (l+r)>>1;
    mp = mp1;
   // cout << l << " " << r << endl;
    if(is_can(md)){
      //cout << md << endl;
      res = md;
      l = md+1;
    }else{
      r = md-1;
    }
  }
  if(res == 0) cout << -1 << endl;
  else cout << res << endl;
}

signed main(){
  solve();
  return 0;
} 

• Subtask 1: 0 / 100