Submission #886609

#	Time	Username	Problem	Language	Result	Execution time	Memory
886609		gnu	Mecho (IOI09_mecho)	C++17	0 / 100	3 ms	856 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
int n, S;
vector<string> board;
vector<vector<int>> vis;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
struct point{
    int i, j;
    point(int i, int j) {
        this->i = i;
        this->j = j;
    }
};
void solve()
{
    n, S; cin >> n >> S;
    board = vector<string>(n);
    vis = vector<vector<int>> (n, vector<int> (n));
    for (int i = 0; i < n; ++i) cin >> board[i];
    point mecho(0,0), home(0,0);
    vector<point> honey;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'H') honey.emplace_back(i, j);
            else if (board[i][j] == 'M') mecho = {i, j};
            else if (board[i][j] == 'D') home = {i, j};
        }
    }
    queue<point> mq;
    vector<vector<int>> dist(n, vector<int> (n, 0   ));
    for (auto x : honey) {
        mq.push(x);
        vis[x.i][x.j] = 1;
        dist[x.i][x.j] = 0;
    }
    while (!mq.empty()) {
        point u = mq.front();
        mq.pop();
        for (int i = 0; i < 4; ++i) {
            if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || vis[u.i+dx[i]][u.j+dy[i]] || board[u.i+dx[i]][u.j+dy[i]] == 'T') continue;
            mq.emplace(u.i + dx[i], u.j + dy[i]);
            vis[u.i + dx[i]][u.j + dy[i]] = 1;
            dist[u.i + dx[i]][u.j + dy[i]] = dist[u.i][u.j] + 1;
        }
    }
//    for (auto &x : dist)
//    {
//        for (auto y : x) cout << y << ' ';
//        cout << '\n';
//    }

    int l = -1, r = 1e9;
//    return;
    while (l + 1 < r) {
        vector<vector<int>> md(n, vector<int> (n));
        int m = (l + r) / 2;
        vis = vector<vector<int>> (n, vector<int> (n));
        queue<point> q;
        q.emplace(mecho.i, mecho.j);
        vis[mecho.i][mecho.j] = 1;
        if (m >= dist[mecho.i][mecho.j]) q.pop();
        while (!q.empty()) {
            point u = q.front();

            q.pop();
            for (int i = 0; i < 4; ++i) {
                int ni = u.i + dx[i], nj = u.j + dy[i];
                if (((md[u.i][u.j]+1) / S >= (dist[u.i][u.j] - m))) continue;
                if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || vis[u.i+dx[i]][u.j+dy[i]] || board[u.i+dx[i]][u.j+dy[i]] != 'G') continue;
                q.emplace(ni, nj);
                md[ni][nj] = md[u.i][u.j] + 1;
                vis[ni][nj] = 1;
            }
        }
        bool ok = false;
        for (int i = 0; i < 4; ++i) {
            point u = home;
            if (((md[u.i][u.j]+1) / S >= (dist[u.i][u.j] - m))) continue;
            if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || board[u.i+dx[i]][u.j+dy[i]] != 'G') continue;
            if (vis[home.i + dx[i]][home.j+dy[i]]) ok = true;
        }
        if (ok) {
            l = m;
        } else r = m;
            
    }
    cout << l;

}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    solve();
}

Compilation message (stderr)

mecho.cpp: In function 'void solve()':
mecho.cpp:17:5: warning: left operand of comma operator has no effect [-Wunused-value]
   17 |     n, S; cin >> n >> S;
      |     ^
mecho.cpp:17:9: warning: right operand of comma operator has no effect [-Wunused-value]
   17 |     n, S; cin >> n >> S;
      |         ^
mecho.cpp: In function 'int main()':
mecho.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100