Submission #1205992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205992		lxz20071231	Mecho (IOI09_mecho)	C++20	28 / 100	747 ms	6952 KiB

mecho

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

using ll = long long; using db = double;
template <class T> using v = vector<T>;
using pii = pair<int, int>; using vi = v<int>; using vpi = v<pii>; using vvi = v<vi>; using vvpi = v<vpi>;
using pll = pair<ll, ll>; using vll = v<ll>; using vpl = v<pll>; using vvl = v<vll>; using vvpl = v<vpl>;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()

const int INF = 1e9;
const ll INFLL = 1e18;

const int N = 801;
int n, s, dist[N][N];
pii start, fin;
string grid[N];
bool vis[N][N];

vpi adjacent(int y, int x){
    vpi adj;
    if (y > 0){
        if (grid[y-1][x] != 'H' && grid[y-1][x] != 'T') adj.pb({y-1, x});
    }
    if (x > 0){
        if (grid[y][x-1] != 'H' && grid[y][x-1] != 'T') adj.pb({y, x-1});
    }
    if (y < n-1){
        if (grid[y+1][x] != 'H' && grid[y+1][x] != 'T') adj.pb({y+1, x});
    }
    if (x < n-1){
        if (grid[y][x+1] != 'H' && grid[y][x+1] != 'T') adj.pb({y, x+1});
    }
    return adj;
}

bool check(int t){
    if (t*s >= dist[start.f][start.s]) return false;
    vvi d(n, vi(n, 0));
    v<v<bool>> processed(n, v<bool>(n, false));
    d[start.f][start.s] = t * s;
    processed[start.f][start.s] = true;

    queue<pii> q;
    q.push(start);
    while (!q.empty()){
        auto [y, x] = q.front(); q.pop();
        for (auto [y1, x1] : adjacent(y, x)){
            if (!processed[y1][x1] && d[y][x]+1 < dist[y1][x1]){
                if (mp(y1-1, x1) == fin || mp(y1+1, x1) == fin || mp(y1, x1-1) == fin || mp(y1, x1+1) == fin){
                    return true;
                }
                d[y1][x1] = d[y][x]+1;
                processed[y1][x1] = true;
                q.push({y1, x1});
            }
        }
    }
    
    return false;
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    
    cin >> n >> s;
    queue<pii> q;
    
    for (int y=0; y<n; y++){
        cin >> grid[y];
        for (int x=0; x<n; x++){
            if (grid[y][x] == 'M'){
                start = {y, x};
            }
            else if (grid[y][x] == 'D'){
                fin = {y, x};
            }
            else if (grid[y][x] == 'H'){
                vis[y][x] = true;
                q.push({y, x});
            }
        }
    }

    while (!q.empty()){
        auto [y, x] = q.front(); q.pop();
        for (auto [y1, x1] : adjacent(y, x)){
            if (!vis[y1][x1]){
                vis[y1][x1] = true;
                dist[y1][x1] = dist[y][x] + s;
                q.push({y1, x1});
            }
        }
    }

    if (!check(0)){
        cout << "-1\n";
    }
    else{
        int l = 0, r = 1e9;
        while (l < r){
            int mid = (l+r+1)/2;
            if (check(mid)) l = mid;
            else r = mid-1;
        }
        cout << l << '\n';
    }

    
    return 0;
}

• Subtask 1: 28 / 100