Submission #482932

#	Time	Username	Problem	Language	Result	Execution time	Memory
482932		PacifiedPenguin	Mecho (IOI09_mecho)	C++17	100 / 100	381 ms	6852 KiB

mecho

#include <bits/stdc++.h>
using P = std::pair<int, int>;
const int INF = 1e9;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int32_t main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
    int N, S; std::cin >> N >> S;
    std::vector<std::string> a(N);
    P start, end;

    std::vector<std::vector<int>> dpB(N, std::vector<int>(N, INF));
    std::queue<P> qb;
    for(int i = 0; i < N; i++){
        std::cin >> a[i];
        for(int j = 0; j < N; j++){
            if(a[i][j] == 'M'){
                start = P(i, j);
                a[i][j] = 'G';
            }else if(a[i][j] == 'D'){
                end = P(i, j);
            }else if(a[i][j] == 'H'){
                qb.emplace(i, j);
                dpB[i][j] = 0;
            }
        }
    }

    while(!qb.empty()){
        P tp = qb.front(); qb.pop();
        for(int i = 0; i < 4; i++){
            int nx = tp.first + dx[i];
            int ny = tp.second + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(a[nx][ny] == 'G'){
                if(dpB[nx][ny] > dpB[tp.first][tp.second] + S){
                    dpB[nx][ny] = dpB[tp.first][tp.second] + S;
                    qb.emplace(nx, ny);
                }
            }
        }
    }

    std::vector<std::vector<int>> dp = dpB;
    auto check = [&](int delay) -> bool{
        int tickStart = delay * S;
        if(tickStart >= dpB[start.first][start.second]) return false;
        // can only walk through regions wich tick value less
        for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) dp[i][j] = INF;
        std::queue<P> q;
        q.push(start); dp[start.first][start.second] = tickStart;
        while(!q.empty()){
            P tp = q.front(); q.pop();
            if(tp == end) return true;
            for(int i = 0; i < 4; i++){
                int nx = tp.first + dx[i];
                int ny = tp.second + dy[i];
                if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if(dpB[nx][ny] <= dp[tp.first][tp.second] + 1) continue;
                if(a[nx][ny] == 'G' || a[nx][ny] == 'D'){
                    if(dp[nx][ny] > dp[tp.first][tp.second] + 1){
                        dp[nx][ny] = dp[tp.first][tp.second] + 1;
                        q.emplace(nx, ny);
                    }
                }
            }
        }
        return false;
    };

    if(!check(0)){
        std::cout << "-1\n";
        return 0;
    }

    int l = -1, h = 1;
    while(check(h)) h *= 2;
    while(l < h){
        int mid = l + (h - l + 1) / 2;
        if(check(mid)){
            l = mid;
        }else{
            h = mid - 1;
        }
    }
    std::cout << l << '\n';
    return 0;
}

• Subtask 1: 100 / 100