Submission #1257209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257209		satyanshu	Mecho (IOI09_mecho)	C++20	100 / 100	149 ms	8784 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 7;
bool bipartite;
const int MAXN = 200005;
ll fact[MAXN];
ll h, c, t;
const ll NEG_INF = -1e17 - 7;

bool is_valid(int x, int y, int n, int m){
    return x >= 0 && x < n && y >= 0 && y < m;
}

bool f(int wait_time, vector<vector<int>> &dis1, vector<vector<int>> &dis2, vector<string> &a, int home_x, int home_y, int n, int s, int mecho_x, int mecho_y){
     int del_x[4] = {-1, 0, 0, 1};
     int del_y[4] = {0, -1, 1, 0};

     if (wait_time >= dis2[mecho_x][mecho_y]) return false;

     queue<pair<pair<int,int>,int>>q;
     q.push({{mecho_x, mecho_y}, 0});

     vector<vector<int>>vis(n, vector<int>(n));
     vis[mecho_x][mecho_y] = 1;

     while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int steps = q.front().second;
        q.pop();

        if(x == home_x && y == home_y) return true;

        for(int i=0;i<4;i++){
            int new_x = x + del_x[i];
            int new_y = y + del_y[i];
            int new_steps = steps + 1;

            if(!is_valid(new_x, new_y, n, n)) continue;
            if(vis[new_x][new_y]) continue;
            if(!(a[new_x][new_y] == 'G' || a[new_x][new_y] == 'D' || a[new_x][new_y] == 'M')) continue;

            int arrival_time = wait_time + ( (new_steps) / s );
            if(arrival_time < dis2[new_x][new_y]){
                 vis[new_x][new_y] = 1;
                 q.push({{new_x, new_y}, new_steps});
            }
        }
     }

     return false;

     
}

void solve()
{
    int n, s;
    cin >> n >> s;

    vector<string> a(n);
    int mecho_x = 0, mecho_y = 0, home_x = 0, home_y = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] == 'M')
            {
                mecho_x = i;
                mecho_y = j;
            }
            if (a[i][j] == 'D')
            {
                home_x = i;
                home_y = j;
            }
        }
    }

    vector<vector<int>> dis1(n, vector<int>(n, INF));
    dis1[mecho_x][mecho_y] = 0;
    queue<pair<int, int>> q;
    q.push({mecho_x, mecho_y});

    int del_x[4] = {-1, 0, 0, 1};
    int del_y[4] = {0, -1, 1, 0};

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0;i<4;i++){
            int new_x = x + del_x[i];
            int new_y = y + del_y[i];

            if(is_valid(new_x, new_y, n, n) && (a[new_x][new_y] == 'G' || a[new_x][new_y] == 'D') && dis1[new_x][new_y] > dis1[x][y] + 1){
                dis1[new_x][new_y] = dis1[x][y] + 1;
                q.push({new_x, new_y});
            }
        }
    }

    vector<vector<int>>dis2(n, vector<int>(n, INF));
    queue<pair<int,int>>q2;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j] == 'H'){
                q2.push({i, j});
                dis2[i][j] = 0;
            }
        }
    }

    while(!q2.empty()){
        int x = q2.front().first;
        int y = q2.front().second;
        q2.pop();

        for(int i=0;i<4;i++){
            int new_x = x + del_x[i];
            int new_y = y + del_y[i];

            if(is_valid(new_x, new_y, n, n) && (a[new_x][new_y] == 'G' || a[new_x][new_y] == 'M' || a[new_x][new_y] == 'H') && dis2[new_x][new_y] > dis2[x][y] + 1){
                dis2[new_x][new_y] = dis2[x][y] + 1;
                q2.push({new_x, new_y});
            }
        }
    }

    int low = 0, high = 1e9, ans = -1;
    while(low <= high){
        int mid = (low + high)/2;

        if(f(mid, dis1, dis2, a, home_x, home_y, n, s, mecho_x, mecho_y)){
            ans = mid;
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
    }

    cout<<ans<<endl;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100