Submission #1188071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188071		Owstin	Mecho (IOI09_mecho)	C++20	60 / 100	1097 ms	33292 KiB

mecho

#include <bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int b, c; cin >> b >> c;
    vector<vector<char>> vec(b, vector<char>(b));
    queue<pair<int, pair<int, int>>> q;
    pair<int, int> start; pair<int, int> dest;
    for (int i = 0; i < b; i++) {
        for (int j = 0; j < b; j++) {
            cin >> vec[i][j];
            if (vec[i][j] == 'H') {
                q.push({0, {i, j}});
            }
            if (vec[i][j] == 'M') {
                start = {i, j};
            }
            if (vec[i][j] == 'D') {
                dest = {i, j};
            }
        }
    }
    vector<vector<int>> dist(b, vector<int>(b, INT32_MAX));
    while (!q.empty()) {
        auto curr = q.front(); q.pop(); int x = curr.second.first; int y = curr.second.second;
        if (x < 0 || y < 0 || x >= b || y >= b || curr.first > dist[x][y] || vec[x][y] == 'T' || vec[x][y] == 'D') {
            continue;
        }
        if (x < b - 1 && dist[x + 1][y] == INT32_MAX && vec[x + 1][y] != 'T' && vec[x + 1][y] != 'D') {
            q.push({curr.first + 1, {x + 1, y}});
            dist[x + 1][y] = curr.first + 1;
        }
        if (y < b - 1 && dist[x][y + 1] == INT32_MAX && vec[x][y + 1] != 'T' && vec[x][y + 1] != 'D') {
            q.push({curr.first + 1, {x, y + 1}});
            dist[x][y + 1] = curr.first + 1;
        }
        if (x > 0 && dist[x - 1][y] == INT32_MAX && vec[x - 1][y] != 'T' && vec[x - 1][y] != 'D') {
            q.push({curr.first + 1, {x - 1, y}});
            dist[x - 1][y] = curr.first + 1;
        }
        if (y > 0 && dist[x][y - 1] == INT32_MAX && vec[x][y - 1] != 'T' && vec[x][y - 1] != 'D') {
            q.push({curr.first + 1, {x, y - 1}});
            dist[x][y - 1] = curr.first + 1;
        }
    }
    int lo = 0; int hi = b * b; int res = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        bool flag = false;
        set<pair<int, int>> visited;
        queue<pair<int, pair<int, int>>> q;
        q.push({0, start});
        while (!q.empty()) {
            auto curr = q.front(); q.pop(); int x = curr.second.first; int y = curr.second.second;
            if (x == dest.first && y == dest.second) {
                flag = true; break;
            }
            if (x < 0 || y < 0 || x >= b || y >= b || vec[x][y] == 'T' || curr.first / c >= dist[x][y] - mid) {
                continue;
            }
            if (!visited.count({x - 1, y})) {
                q.push({curr.first + 1, {x - 1, y}});
                visited.insert({x - 1, y});
            }
            if (!visited.count({x, y - 1})) {
                q.push({curr.first + 1, {x, y - 1}});
                visited.insert({x, y - 1});
            }
            if (!visited.count({x + 1, y})) {
                q.push({curr.first + 1, {x + 1, y}});
                visited.insert({x + 1, y});
            }
            if (!visited.count({x, y + 1})) {
                q.push({curr.first + 1, {x, y + 1}});
                visited.insert({x, y + 1});
            }
        }
        if (flag) {
            res = mid;
            lo = mid + 1;
        }
        else {
            hi = mid - 1;
        }
    }
    cout << res;
}
int main() {
    FAST_IO;
    //freopen("atlarge.in", "r", stdin);
    //freopen("atlarge.out", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}

• Subtask 1: 60 / 100