Submission #1235600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235600		lechaa	Mecho (IOI09_mecho)	C++20	100 / 100	224 ms	6284 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, s; cin >> n >> s;
    vector<string> g(n);
    for(int i = 0; i < n; i++){
        cin >> g[i];
    }
    queue<pair<int, pair<int, int>>> q;
    pair<int, int> it;
    pair<int, int> it1;
    for(int i = 0; i < n; i++){
        for(int y = 0; y < n; y++){
            if(g[i][y] == 'H'){
                q.push({i, {y, -1}});
            }else if(g[i][y] == 'M'){
                it = {i, y};
            }else if(g[i][y] == 'D'){
                it1 = {i, y};
            }
        }
    }
    vector<vector<int>> d(n, vector<int>(n, 1e9));
    while(q.size() > 0){
        int x = q.front().first;
        int y = q.front().second.first;
        int time = q.front().second.second;
        q.pop();
        if(x < 0 || y < 0 || x >= n || y >= n){
            continue;
        }
        if(d[x][y]  != 1e9) continue;
        if(g[x][y] == 'T' || g[x][y] == 'D'){
            continue;
        }
        d[x][y] = time+1;
        q.push({x-1, {y, d[x][y]}});
        q.push({x+1, {y, d[x][y]}});
        q.push({x, {y+1, d[x][y]}});
        q.push({x, {y-1, d[x][y]}});
    }
    int low = 0;
    int top = n*n;
    int ns = -1;
    while(low <= top){
        int mid = (low + top)/2;
        vector<vector<int>> d1(n, vector<int>(n, 1e9));
        queue<pair<int, pair<int, int>>> q;
        q.push({it.first, {it.second, -1}});
        while(q.size() > 0){
            int x = q.front().first;
            int y = q.front().second.first;
            int time = q.front().second.second;
            q.pop();
            if(x < 0 || y < 0 || x >= n || y >= n){
                continue;
            }
            if(d1[x][y]  != 1e9) continue;
            if(g[x][y] == 'T'){
                continue;
            }
            if(d[x][y] < mid + (time+1)/s + 1 && d[x][y] != 1e9){
                continue;
            }
            d1[x][y] = time+1;
            q.push({x-1, {y, d1[x][y]}});
            q.push({x+1, {y, d1[x][y]}});
            q.push({x, {y+1, d1[x][y]}});
            q.push({x, {y-1, d1[x][y]}});
        }
        if(d1[it1.first][it1.second] != 1e9){
            low = mid+1;
            ns = mid;
        }else{
            top = mid-1;
        }
    }
    cout << ns << "\n";
    return 0;
}

• Subtask 1: 100 / 100