Submission #999666

#	Time	Username	Problem	Language	Result	Execution time	Memory
999666		a5a7	Mecho (IOI09_mecho)	C++14	100 / 100	191 ms	11392 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> 
using indexedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, s;
    cin >> n >> s;
    vector<vector<char>> grid(n, vector<char>(n));
    queue<pair<ll, pair<int, int>>> h;
    pair<int, int> m;
    pair<int, int> dest;
    vector<pair<int, int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    vector<vector<ll>> dist(n, vector<ll>(n, 1e9));

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> grid[i][j];
            if (grid[i][j] == 'H'){
                h.push({0, {i, j}});
                dist[i][j] = 0;
            }
            if (grid[i][j] == 'M'){
                m = {i, j};
            }
            if (grid[i][j] == 'D'){
                dest = {i, j};
            }
        }
    }

    while (!h.empty()){
        int x = h.front().second.first;
        int y = h.front().second.second;
        ll d = h.front().first;
        h.pop();
        if (dist[x][y] != d) continue;
        for (auto ne : dir){
            int nx = x + ne.first;
            int ny = y + ne.second;
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if ((grid[nx][ny] == 'G' || grid[nx][ny] == 'M') && dist[nx][ny] > (d+1)){
                h.push({d+1, {nx, ny}});
                dist[nx][ny] = d+1;
            }
        }
    }
    function<bool(int)> works = [&](ll t){
        queue<pair<ll, pair<int, int>>> q;
        vector<vector<ll>> di(n, vector<ll>(n, 1e9));
        if ((dist[m.first][m.second]-t) <= 0){
            return false;
        }
        di[m.first][m.second] = 0;
        q.push({0, m});
        while (!q.empty()){
            int x = q.front().second.first;
            int y = q.front().second.second;
            ll d = q.front().first;
            q.pop();
            if (di[x][y] != d) continue;
            for (auto ne : dir){
                int nx = x + ne.first;
                int ny = y + ne.second;
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if ((grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && di[nx][ny] > (d+1) && (d+1) < s*(-t+dist[nx][ny])){
                    q.push({d+1, {nx, ny}});
                    di[nx][ny] = d+1;
                }
            }
        }
        if (di[dest.first][dest.second] == 1e9){
            return false;
        }
        return true;
    };
    ll l = -1, r = n*n;
    while (l < r){
        ll m = (l+r+1)/2;
        if (works(m)){
            l = m;
        }else{
            r = m-1;
        }
    }
    cout << l << endl;
}

• Subtask 1: 100 / 100