Submission #1247345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247345		anha3k25cvp	Mecho (IOI09_mecho)	C++20	84 / 100	185 ms	15648 KiB

mecho

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const int inf = 7 + 2e9;

int n, len, s_x, s_y, t_x, t_y;
vector <vector <int>> a, h;

int dr[] = {-1, 0, 0, 1};
int dc[] = {0, -1, 1, 0};

int check(int lim) {
    vector <vector <int>> f(n + 1, vector <int>(n + 1, inf));
    queue <II> q;
    q.push({s_x, s_y});
    f[s_x][s_y] = lim * len;
    while (!q.empty()) {
        int x = q.front().st, y = q.front().nd;
        q.pop();
        for (int i = 0; i < 4; i ++) {
            int u = x + dr[i], v = y + dc[i];
            if (u < 1 || u > n || v < 1 || v > n || a[u][v] || f[u][v] <= f[x][y] + 1 || h[u][v] <= f[x][y] + 1)
                continue;
            if (u == t_x && v == t_y)
                return 1;
            q.push({u, v});
            f[u][v] = f[x][y] + 1;
        }
    }
    return 0;
}

int32_t main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    queue <II> q;
    cin >> n >> len;
    a.assign(n + 1, vector <int>(n + 1, 0));
    h.assign(n + 1, vector <int>(n + 1, inf));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            char c;
            cin >> c;
            if (c == 'T')
                a[i][j] = 1;
            else if (c == 'M') {
                s_x = i;
                s_y = j;
            }
            else if (c == 'D') {
                t_x = i;
                t_y = j;
            }
            else if (c == 'H') {
                a[i][j] = 1;
                q.push({i, j});
                h[i][j] = 0;
            }
        }
    while (!q.empty()) {
        int x = q.front().st, y = q.front().nd;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int u = x + dr[i], v = y + dc[i];
            if (u < 1 || u > n || v < 1 || v > n || a[u][v] || h[u][v] <= h[x][y] + len || (u == t_x && v == t_y))
                continue;
            q.push({u, v});
            h[u][v] = h[x][y] + len;
        }
    }
    int lo = -1, hi = n * n * len;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (check(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    cout << lo;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:46:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:47:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 84 / 100