Submission #1027016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027016		lmToT27	Mecho (IOI09_mecho)	C++14	95 / 100	112 ms	7152 KiB

mecho

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 8e2 + 3;
const ll MOD[] = {1000000007, 998244353};

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char a[MAX][MAX];
int n, s;
int badTime[MAX][MAX];
bool vs[MAX][MAX];
int d[MAX][MAX];

bool ok(int i, int j) {
        return i && j && max(i, j) <= n && a[i][j] != 'T';
}

void Solve() {
        cin >> n >> s;
        pair <int, int> house;
        pair <int, int> start;
        queue <pair <int, int>> q;
        for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                        cin >> a[i][j];
                        if (a[i][j] == 'D') house = {i, j};
                        if (a[i][j] == 'M') start = {i, j};
                        if (a[i][j] == 'H') {
                                vs[i][j] = 1;
                                q.push({i, j});
                        }
                }
        }
        
        while (q.size()) {
                auto [u, v] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                        int x = u + dx[i];
                        int y = v + dy[i];
                        if (ok(x, y) && !vs[x][y]) {
                                vs[x][y] = 1;
                                badTime[x][y] = badTime[u][v] + 1;
                                q.push({x, y});
                        }
                }
        }

        auto check = [&](int val) -> bool {
                memset(vs, 0, sizeof vs);
                memset(d, 0, sizeof d);

                vs[start.first][start.second] = 1;
                queue <pair <int, int>> q;
                q.push(start);
                
                while (q.size()) {
                        if (q.front() == house) return 1;
                        auto [u, v] = q.front();
                        q.pop();
                        for (int i = 0; i < 4; i++) {
                                int x = u + dx[i];
                                int y = v + dy[i];
                                if (ok(x, y)) {
                                        if (make_pair(x, y) == house) return 1;
                                        if (vs[x][y] == 0 && (badTime[x][y] - (d[u][v] + 1) / s - 1) >= val) {
                                                vs[x][y] = 1;
                                                q.push({x, y});
                                                d[x][y] = d[u][v] + 1;
                                        }
                                }
                        }
                }
                
                return 0;
        };

        int ans = -1;
        int l = 0, r = badTime[start.first][start.second] - 1;

        while (l <= r) {
                int mid = (l + r) / 2;
                if (check(mid)) {
                        l = mid + 1;
                        ans = mid;
                } else r = mid - 1;
        }
        cout << ans;
}

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        #define TASK "TASK"
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }
        
        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}       

Compilation message (stderr)

mecho.cpp: In function 'void Solve()':
mecho.cpp:54:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |                 auto [u, v] = q.front();
      |                      ^
mecho.cpp: In lambda function:
mecho.cpp:77:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |                         auto [u, v] = q.front();
      |                              ^
mecho.cpp: In function 'int32_t main()':
mecho.cpp:115:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:116:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 95 / 100