Submission #1180569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180569		t_danh	Mecho (IOI09_mecho)	C++20	100 / 100	269 ms	6324 KiB

mecho

/*
 ██████████        ███████                       ██  
░░░░░██░░░        ░██░░░░██                     ░██  
    ░██           ░██    ░██   ██████   ███████ ░██  
    ░██           ░██    ░██  ░░░░░░██ ░░██░░░██░██████
    ░██           ░██    ░██   ███████  ░██  ░██░██░░░██
    ░██           ░██    ██   ██░░░░██  ░██  ░██░██  ░██
    ░██     █████ ░███████   ░░████████ ███  ░██░██  ░██
    ░░     ░░░░░  ░░░░░░░     ░░░░░░░░ ░░░   ░░ ░░   ░░
*/
 
#include <bits/stdc++.h>
#define input  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ce cout << endl
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
using namespace std;
using ll = long long;
using str = string;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
 
const ll N = 1e5+1;
const ll LOGN = 19;
const int INF = numeric_limits<int>::max();
const ll MOD = 998244353;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char op[] = {'D','U','R','L'};
void solve() {
    int n , s;
    cin >> n >> s;
    vector<vector<char>> matrix(n,vector<char>(n));
    vector<pii> hives;
    pii mecho;
    pii end;
    FOR(i,0,n-1){
        FOR(j,0,n-1) 
        {
            cin >> matrix[i][j];
            if(matrix[i][j] == 'H') hives.pb({i,j});
            else if(matrix[i][j] == 'M') mecho ={i,j};
            else if(matrix[i][j] == 'D') end = {i,j};
        }
    }
    function<bool(int,int)> inside =[&] (int i ,int j){
        return (i > - 1 && i < n && j > -1 && j < n && matrix[i][j] != 'T' && matrix[i][j] != 'H' && matrix[i][j] != 'D' );
    };
    function<bool(int,int)> check =[&] (int time,int dist){
        return time / s < dist;
    };
    

    queue<pii> q;
    vector<vector<int>> bee_time(n,vector<int>(n,-1));


    for(auto &i : hives){
        q.push(i);
        bee_time[i.fi][i.se] = 0;
    }
    while(!q.empty()){
        pii c = q.front();
        q.pop();
        for(int i = 0 ; i < 4 ;  i++){
            int x = c.fi + dx[i] , y = c.se + dy[i];
            if(inside(x,y) && bee_time[x][y] == -1){
                bee_time[x][y] = bee_time[c.fi][c.se] + 1;
                q.push({x,y});
            }
        }
    }
    int l = -1 ;
    int h = n * n;
    while( l < h){
        int eating_time = l + h + 1 >> 1;
        vector<vector<int>> mecho_time(n,vector<int>(n));
		vector<vector<bool>> mecho_visited(n, vector<bool>(n));

        // move Mecho
		q.push({mecho.fi, mecho.se});
		mecho_visited[mecho.fi][mecho.se] = true;
		if (bee_time[mecho.fi][mecho.se] <= eating_time) { q.pop(); }

		while (!q.empty()) {
			int x = q.front().first, y = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				/*
				 * check if mecho reaces node[x][y] before the bees
				 * divide the time mecho takes to reach a node by s, since
				 * mecho walks s steps at a time.
				 * substract the eating time from the time taken for the
				 * bees to reach the node, because that time was used by
				 * mecho for eating
				 */
				if (inside(nx, ny) && !mecho_visited[nx][ny] &&
				    check(mecho_time[x][y] + 1,
				                  bee_time[nx][ny] - eating_time)) {
					mecho_visited[nx][ny] = true;
					q.push({nx, ny});
					mecho_time[nx][ny] = mecho_time[x][y] + 1;
				}
			}
		}

		bool reached = false;
		for (int i = 0; i < 4; i++) {
			int nx = end.fi + dx[i], ny = end.se + dy[i];
			if (inside(nx, ny) &&
			    check(mecho_time[nx][ny], bee_time[nx][ny] - eating_time) &&
			    mecho_visited[nx][ny]) {
				reached = true;
			}
		}
		if (reached) 
			l = eating_time;
		else 
			h = eating_time - 1;
        
    }
    cout << l <<endl;
}




 
int main() {
    input
    const bool cap = true;


    if (cap)
        solve();    
    else {
        ll t;
        cin >> t;
        while (t--) solve();
    }
}

• Subtask 1: 100 / 100