제출 #712030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712030		Narka	Mecho (IOI09_mecho)	C++14	22 / 100	160 ms	5900 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"
int mp[801][801];
vector<array<int, 2>> hives;
int st[2], nd[2];
int n, s;
queue<array<int, 2>> q;

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(){
  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){
  vector<vector<bool>> vis(805, vector<bool>(805, false));
  q.push({st[0], st[1]});
  if(mp[st[0]][st[1]] <= v) return false;
  vis[st[0]][st[1]] = true;
  int t = 1, b = 0, stp = 1, c = 0;
  while(!q.empty()){
    array<int, 2> tt = q.front(); q.pop(), t--;  
    rep(i, 0, 3){
     int x = tt[0] + dx[i];
     int y = tt[1] + dy[i];
     if(safe(x, y)&& !vis[x][y] && stp + v < mp[x][y] ){
      if(x == nd[0] && y == nd[1]) return true;
      b++;
      q.push({x, y});
      vis[x][y] = true;
     } 
    }
    if(t == 0){
      t = b; c++; b = 0;
    }
    if(c == s){
      c = 0; stp++;
    }
  }
  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[0] = i, st[1] = j;
      else if(a[j] == 'H') mp[i][j] = 1, hives.pb({i, j});
      else if(a[j] == 'D') nd[0] = i, nd[1] = j;
    }
  }
  attack();
  int l = 0, r = mp[st[0]][st[1]] + 1, res = 0;
  while(l <= r){
    int md = (l+r)>>1;
    queue<array<int, 2>> empty;
    swap( q, empty );
    if(is_can(md)){
      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: 22 / 100