Submission #995506

#	Time	Username	Problem	Language	Result	Execution time	Memory
995506		phoenix	Mecho (IOI09_mecho)	C++17	100 / 100	145 ms	14432 KiB

mecho

#include<bits/stdc++.h>

using namespace std;
const int INF = 1e8;

vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, +1}};
int n, s;
char c[1000][1000];
int f[1000][1000];
pair<int, int> st, fi;
bool inside(pair<int, int> g) {
    return (min(g.first, g.second) >= 0 && max(g.first, g.second) < n);
}

int t[1000][1000], step[1000][1000];
bool vis[1000][1000];

bool check(int T) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            step[i][j] = 0;
            t[i][j] = INF;
            vis[i][j] = false;
        }
    }
    t[st.first][st.second] = T;
    vis[st.first][st.second] = 1;

    queue<pair<int, int>> q;
    q.push(st);
    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if(c[x][y] == 'D') return 1;
        if(t[x][y] > f[x][y] || (!step[x][y] && t[x][y] == f[x][y])) 
            continue;
         
        for(auto [dx, dy] : dirs) { 
            pair<int, int> to = {x + dx, y + dy};
            if(!inside(to) || vis[to.first][to.second]) continue;
            vis[to.first][to.second] = true;    
            t[to.first][to.second] = t[x][y] + (step[x][y] == 0);
            step[to.first][to.second] = (step[x][y] + 1) % s;
            q.push(to);
        }
    }

    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> s;

    queue<pair<int, int>> h;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> c[i][j];
            if(c[i][j] == 'H') {
                h.push({i, j});
                vis[i][j] = true;
            }
            if(c[i][j] == 'M') 
                st = {i, j};
            if(c[i][j] == 'D') {
                fi = {i, j};
                vis[i][j] = true;
            }
            if(c[i][j] == 'T') 
                vis[i][j] = true;
        }
    }
    while(!h.empty()) {
        auto [x, y] = h.front();
        h.pop();
        for(auto [dx, dy] : dirs) {
            pair<int, int> to = {x + dx, y + dy};
            if(inside(to) && !vis[to.first][to.second]) {
                vis[to.first][to.second] = true;
                f[to.first][to.second] = f[x][y] + 1;
                h.push(to);
            }
        }
    }
    int l = -1, r = 1e9;
    while(r - l > 1) {
        int m = (l + r) / 2;
        if(check(m)) l = m;
        else r = m;
    }
    cout << l;
}

• Subtask 1: 100 / 100