Submission #697391

#	Time	Username	Problem	Language	Result	Execution time	Memory
697391		europium	Mecho (IOI09_mecho)	C++17	15 / 100	191 ms	6212 KiB

mecho

// - 9/2/23
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <iterator>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <unordered_set>
#include <queue>
#include <climits>
using namespace std;
// clang++ -std=c++17 IOI2009_mecho.cpp && ./a.out

using ll = long long;
const int INF = 1e9;
const int dx[] {0, 1, 0, -1};
const int dy[] {1, 0, -1, 0};
int n, s;
int start_x, start_y, end_x, end_y;
vector<vector<char>> grid;
vector<vector<int>> bee;

bool valid(int x, int y){
    return (x >= 0 && x < n && y >= 0 && y < n);
}

void get_bee_dist(){
    queue<tuple<int,int,int>> q;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (grid[i][j] == 'H'){
                bee[i][j] = 0;
                q.push({i, j, 0});
            }
        }
    }

    while (!q.empty()){
        int x, y, d;
        tie(x, y, d) = q.front();
        q.pop();

        for (int k = 0; k < 4; k++){
            int i = x + dx[k], j = y + dy[k];

            if (!valid(i, j) || grid[i][j] == 'T' || bee[i][j] <= d + 1) continue;

            bee[i][j] = min(bee[i][j], d + 1);
            q.push({i, j, d + 1});
        }
    }
}

bool f(int p){
    vector<vector<int>> mecho(n, vector<int> (n, INF));

    queue<tuple<int,int,int>> q;
    mecho[start_x][start_y] = s - 1;
    q.push({start_x, start_y, s - 1});

    while (!q.empty()){
        int x, y, d;
        tie(x, y, d) = q.front();
        q.pop();

        for (int k = 0; k < 4; k++){
            int i = x + dx[k], j = y + dy[k];

            if (!valid(i, j) || grid[i][j] == 'T' || mecho[i][j] <= d + 1 || ((d + 1) / s) + p >= bee[i][j]) continue;

            mecho[i][j] = min(mecho[i][j], d + 1);
            q.push({i, j, d + 1});
        }
    }

    // cout << p << '\n';
    //
    // for (int i = 0; i < n; i++){
    //     for (int j = 0; j < n; j++) cout << (mecho[i][j] / s) + p << ' ';
    //     cout << '\n';
    // }

    return mecho[end_x][end_y] == INF;
}

void solve(){
    cin >> n >> s;

    grid.resize(n, vector<char>(n));
    bee.resize(n, vector<int> (n, INF));

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> grid[i][j];
            if (grid[i][j] == 'M') {start_x = i; start_y = j;}
            if (grid[i][j] == 'D') {end_x = i; end_y = j;}
        }
    }

    get_bee_dist();

    int l = -1, r = n * n, ans, mid;

    while (l < r){
        mid = l + (r - l) / 2;
    	f(mid) ? r = mid : l = mid + 1;
    }

    ans = l;

    // for (int i = 0; i < n; i++){
    //     for (int j = 0; j < n; j++) cout << bee[i][j] << ' ';
    //     cout << '\n';
    // }

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen("input.txt", "r", stdin);
    solve();

    return 0;
}

• Subtask 1: 15 / 100