Submission #530362

#	Time	Username	Problem	Language	Result	Execution time	Memory
530362		Sharky	Mecho (IOI09_mecho)	C++17	73 / 100	220 ms	6812 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N = 805, dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
int n, s;
pair<int, int> src, dest;
vector<string> a(N); vector<vector<int> > dist(N, vector<int> (N, -1));
vector<pair<int, int> > hive; vector<vector<bool> > vis(N, vector<bool> (N, false));
bool ok(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < n && (a[x][y] == 'G' || a[x][y] == 'M' || a[x][y] == 'D'));
}
struct node {
    int x, y, t; 
    node(int a, int b, int c) {
        x = a, y = b, t = c;
    }
};
bool check(int t) {
    // cout << t << "\n";
    queue<node> q; 
    for (int i = 0; i < n; i++) { fill(vis[i].begin(), vis[i].end(), false); }
    // for (auto& [fi, se] : hive) q.push(node(fi, se, 0)), vis[fi][se] = false;
    q.push(node(src.fi, src.se, 0)); vis[src.fi][src.se] = true;
    while (!q.empty()) {
        auto now = q.front();
        q.pop();
        // if (t == 24) cout << now.x << " " << now.y << " " << now.t << "\n";
        for (int i = 0; i < 4; i++) {
            int x = now.x + dx[i];
            int y = now.y + dy[i];
            // walk first then bees go
            // bees are at place (now.t - 1) / s;
            if (!ok(x, y)) continue;
            // cout << now.t / s << " " << dist[x][y] << "\n";
            if (!vis[x][y] && ((now.t + 1) / s) + t < dist[x][y]) {
                vis[x][y] = true;
                q.push(node(x, y, now.t + 1));
            }
        }
    }
    return vis[dest.fi][dest.se];
}
void precompute() {
    queue<pair<int, int> > q;
    for (int i = 0; i < n; i++) { fill(vis[i].begin(), vis[i].end(), false); }
    for (auto& [fi, se] : hive) q.push({fi, se}), vis[fi][se] = true, dist[fi][se] = 0;
    while (!q.empty()) {
        auto now = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = now.fi + dx[i];
            int y = now.se + dy[i];
            if (!ok(x, y)) continue;
            if (!vis[x][y]) {
                vis[x][y] = true;
                q.push({x, y});
                dist[x][y] = dist[now.fi][now.se] + 1;
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'M') src = {i, j};
            if (a[i][j] == 'H') hive.push_back({i, j});
            if (a[i][j] == 'D') dest = {i, j};
        }
    }
    precompute();
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << vis[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    if (!check(0)) { cout << "-1\n"; return 0; }
    int l = 0, r = 1e9;
    while (l < r) {
        int m = (l + r) >> 1;
        if (!check(m)) r = m;
        else l = m + 1;
    }
    cout << l - 1 << "\n";
    return 0;
}

• Subtask 1: 73 / 100