Submission #759170

#	Time	Username	Problem	Language	Result	Execution time	Memory
759170		bane	Mecho (IOI09_mecho)	C++17	84 / 100	158 ms	6412 KiB

mecho

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
 
int n, s, times[802][802];
vector<string> v(802);
pair<int, int> st, en;
 
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
 
inline bool valid(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < n && v[x][y] != 'T' && v[x][y] != 'H');
}
 
bool check(int m) {
    if (m >= times[st.first][st.second]) return 0;
    queue<pair<int, int>> q;
    q.push(st);
    int vis[n + 2][n + 2];
    memset(vis, -1, sizeof(vis));
    vis[st.first][st.second] = 0;

      while (!q.empty()) {
          int x = q.front().first, y = q.front().second;
          q.pop();
          int dist = vis[x][y];
         // cout<<x<<" "<<y<<" "<<dist<<" "<<m<<endl;
          for (int d = 0; d < 4; d++) {
              int nx = x + dx[d], ny = y + dy[d];
              if (valid(nx, ny) && (dist + 1) / s + m< times[nx][ny] && vis[nx][ny] == -1) {
                   vis[nx][ny] = dist+1;
                   q.push({nx, ny});
                   if (make_pair(nx, ny) == en) return 1;
               }
           }
       }
    
    return 0;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> s;
    queue<pair<int, int>> h;
 
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        for (int j = 0; j < n; j++) {
            times[i][j] = (int)1e9;
            if (v[i][j] == 'M') st = {i, j};
            if (v[i][j] == 'H') {
                h.push({i, j});
                times[i][j] = 0;
            }
            if (v[i][j] == 'D') en = {i, j};
        }
    }
 
    while (h.size() > 0) {
        int x = h.front().first, y = h.front().second;
        h.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (valid(nx, ny) && times[x][y] + 1 < times[nx][ny]) {
                times[nx][ny] = times[x][y] + 1;
                h.push({nx, ny});
            }
        }
    }
 
    int l = 0, r = n * n + 100, ans = -1;
    while (l  <= r) {
        int m = (l + r) / 2;
        if (check(m)){
        	 l = m + 1;
        	ans = m;
        }else r = m - 1;
    }
 		cout<<ans;
}

• Subtask 1: 84 / 100