Submission #1046772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046772		daviedu	Mecho (IOI09_mecho)	C++17	100 / 100	118 ms	6928 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const int N = 801; 
char grid[N][N];
int n, s;
vector<vector<int>> bdist (N, vector<int>(N, N*N+1));
pair<int, int> bear;
pair<int, int> home;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
int valid(int x, int y){
    return x >= 0 && y >= 0 && x < n && y < n;
}

int f(int t){
    vector<vector<int>> dist (n, vector<int>(n, n*n+1));
    int x, y;
    queue<pair<int, int>> q;
    dist[bear.first][bear.second] = 0;
    q.push(bear);
    while (!q.empty()){
        tie(x, y) = q.front(); q.pop();
        if ((bdist[x][y]-t)*s <= dist[x][y]) continue;
        for (int i=0; i<4; i++){
            int a = x + dx[i], b = y + dy[i];
            if (!valid(a, b) || grid[a][b] == 'T' || dist[a][b] != n*n+1) continue;
            dist[a][b] = dist[x][y] + 1;
            q.push({a, b});
        }
    }
    return dist[home.first][home.second] != n*n+1;
}

signed main(){
    fastio;
    cin >> n >> s;
    vector<pair<int, int>> bees;
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            cin >> grid[i][j];
            if (grid[i][j] == 'H') bees.push_back({i, j});
            if (grid[i][j] == 'M') bear = {i, j};
            if (grid[i][j] == 'D') home = {i, j};
        }
    }
    int x, y;
    queue<pair<int, int>> q;
    for (auto b: bees){
        q.push(b);
        bdist[b.first][b.second] = 0;
    }
    while (!q.empty()){
        tie(x, y) = q.front(); q.pop();
        for (int i=0; i<4; i++){
            int a = x + dx[i], b = y + dy[i];
            if (!valid(a, b) || grid[a][b] == 'T' || grid[a][b] == 'D' || bdist[a][b] != N*N+1) continue;
            bdist[a][b] = bdist[x][y] + 1;
            q.push({a, b});
        }
    }

    int l=0, r=n*n, ans=-1;
    while (l <= r){
        int m = l + (r-l)/2;
        if (f(m)){
            ans = m;
            l = m+1;
        }
        else r = m-1;
    }

    cout << ans << '\n';
}

• Subtask 1: 100 / 100