Submission #953956

#	Time	Username	Problem	Language	Result	Execution time	Memory
953956		Github	Mecho (IOI09_mecho)	C++17	22 / 100	866 ms	23120 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long

const ll MAXN = 810;
ll bee[MAXN][MAXN];
ll dist[MAXN][MAXN];
pair<ll,ll> parent[MAXN][MAXN];
bool vis[MAXN][MAXN];
ll dX[] = {1, -1, 0, 0};
ll dY[] = {0, 0, 1, -1};
pair<ll, ll> mencho, den;
vector<string> grid;
ll n, s;

bool compute(ll k){
    for (ll i = 0; i < MAXN; i++){
        for (ll j = 0; j < MAXN; j++){
            dist[i][j] = 1e9;
            parent[i][j] = {-1, -1};
            vis[i][j] = false;
        }
    }
    queue<pair<ll, ll>> q;
    q.push(mencho);
    dist[mencho.first][mencho.second] = 0;
    while (!q.empty()){
        ll x = q.front().first, y = q.front().second; q.pop();
        vis[x][y] = true;
        for (ll i = 0; i < 4; i++){
            ll nX = x + dX[i], nY = y+dY[i];
            if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'H'){
                continue;
            }
            if (dist[nX][nY] > dist[x][y]+1 && !vis[nX][nY]){
                dist[nX][nY] = dist[x][y]+1;
                parent[nX][nY] = {x, y};
                q.push({nX, nY});
            }
        }
    }
    pair<ll, ll> cur = parent[den.first][den.second];
    while (cur != make_pair((ll)-1, (ll)-1)){
        if (k+(ll)(dist[cur.first][cur.second]+s-1)/s > bee[cur.first][cur.second]){
            return false;
        }
        cur = parent[cur.first][cur.second];
    }
    return true;
}

int main() {
    speedup
    cin >> n >> s;
    grid.resize(n);
    vector<pair<ll, ll>> start;
    for (ll i = 0; i < n; i++){
        string st; cin >> st;
        grid[i] = st;
        for (ll j = 0; j < n; j++){
            if (st[j] == 'H'){
                start.push_back({i, j});
            }else if (st[j] == 'M'){
                mencho = {i, j};
            }else if (st[j] == 'D'){
                den = {i, j};
            }
        }
    }
    for (ll i = 0; i < MAXN; i++){
        for (ll j = 0; j < MAXN; j++){
            bee[i][j] = 1e9;
            vis[i][j] = false;
        }
    }
    queue<pair<ll, ll>> q;
    for (pair<ll, ll> p: start){
        bee[p.first][p.second] = 0;
        q.push({p.first, p.second});
    }
    while (!q.empty()){
        ll x = q.front().first, y = q.front().second; q.pop();
        vis[x][y] = true;
        for (ll i = 0; i < 4; i++){
            ll nX = x + dX[i], nY = y+dY[i];
            if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'D'){
                continue;
            }
            if (bee[nX][nY] > bee[x][y]+1 && !vis[nX][nY]){
                bee[nX][nY] = bee[x][y]+1;
                q.push({nX, nY});
            }
        }
    }
    ll l = 0, h = 1e9, mid, ans = -1;
    while (l <= h){
        mid = (l+h)/2;
        if (compute(mid)){
            ans = mid;
            l = mid+1;
        }else{
            h = mid-1;
        }
    }
    cout << ans << endl;
    return 0;
}

• Subtask 1: 22 / 100