Submission #656509

#	Time	Username	Problem	Language	Result	Execution time	Memory
656509		prashant_th18	Mecho (IOI09_mecho)	C++17	64 / 100	485 ms	6120 KiB

mecho

#ifdef LOCAL
	#define _GLIBCXX_DEBUG
#endif
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define sz(s) ((int)s.size())
#define all(v) begin(v), end(v)

#ifdef LOCAL
	void debug_print(string s) {
		cerr << "\"" << s << "\"";
	}

	void debug_print(const char* s) {
		debug_print((string)s);
	}

	void debug_print(bool val) {
		cerr << (val ? "true" : "false");
	}

	void debug_print(int val) {
		cerr << val;
	}

	void debug_print(ll val) {
		cerr << val;
	}

	void debug_print(double val) {
		cerr << val;
	}

	template<typename F, typename S>
	void debug_print(pair<F, S> val) {
		cerr << "(";
		debug_print(val.first);
		cerr << ", ";
		debug_print(val.second);
		cerr << ")";
	}

	void debug_print(vector<bool> val) {
		cerr << "{";
		bool first = true;
		for (bool x : val) {
			if (!first) {
				cerr << ", ";
			} else {
				first = false;
			}
			debug_print(x);
		}
		cerr << "}";
	}

	template<typename T>
	void debug_print(T val) {
		cerr << "{";
		bool first = true;
		for (const auto &x : val) {
			if (!first) {
				cerr << ", ";
			} else {
				first = false;
			}
			debug_print(x);
		}
		cerr << "}";
	}

	void debug_print_collection() {
		cerr << endl;
	}

	template<typename First, typename... Args>
	void debug_print_collection(First val, Args... args) {
		cerr << " ";
		debug_print(val);
		debug_print_collection(args...);
	}

#define debug(...) cerr << "@@@ " << #__VA_ARGS__ << " ="; debug_print_collection(__VA_ARGS__);

#else
	#define debug(...) 
#endif

typedef long double ld;
const int MOD = 1000000007;
#define ff first
#define ss second
const int inf = (int)1e9;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
using pll = pair<ll, ll>;

// *-> KISS*
int solve() {
    int n, s; cin >> n >> s;
	vector<string> v(n);
	for(int i = 0; i < n; ++i) cin >> v[i];
	pll start;
	vector<pll> bees;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(v[i][j] == 'M') start = {i, j};
			else if(v[i][j] == 'H') bees.push_back({i, j});
		}
	}
	// Valid function for mecho
	auto mvalid = [&](int i, int j) {
		return i >= 0 && j >= 0 && i < n && j < n && v[i][j] != 'T';
	};
	// valid function for bees
	auto bvalid = [&](int i, int j) {
		return i >= 0 && j >= 0 && i < n && j < n && v[i][j] != 'T';
	};

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

	int ans = -1;
	int si = 0, ei = 100000;
	while(si <= ei) {
		int mid = (si + ei) >> 1;
		// We are assuming that Mecho will stay at it's place for mid minutes and then start moving towards 
		// his home
		vector<vector<bool>> bvis(n, vector<bool>(n, false)), 
			mvis(n, vector<bool>(n, false));
	
		vector<pll> last;
		vector<vector<int>> steps(n, vector<int>(n, inf));
		{
			queue<array<ll, 3>> q;
			for(int i = 0; i < sz(bees); ++i) {
				q.push({bees[i].ff, bees[i].ss, 0});
				bvis[bees[i].ff][bees[i].ss] = true;
			}
			while(!q.empty()) {
				array<ll, 3> t = q.front(); q.pop();
				steps[t[0]][t[1]] = 0;
				if(t[2] == mid) {
					last.push_back({t[0], t[1]});
					continue;
				}

				int x = t[0], y = t[1], step = t[2];

				for(int i = 0; i < 4; ++i) {
					int ni = x + dx[i], nj = y + dy[i];
					if(bvalid(ni, nj) && !bvis[ni][nj]) {
						bvis[ni][nj] = true;
						q.push({ni, nj, step + 1});
					}
				}
			}
		}
		queue<array<ll, 3>> q;
		for(int i = 0; i < sz(last); ++i) {
			q.push({last[i].ff, last[i].ss, 0});
		}
		while(!q.empty()) {
			array<ll, 3> _ = q.front(); q.pop();
			int x = _[0], y = _[1], step = _[2];
			for(int i = 0; i < 4; ++i) {
				int ni = x + dx[i], nj = y + dy[i];
				if(bvalid(ni, nj) && !bvis[ni][nj]) {
					q.push({ni, nj, step + 1});
					steps[ni][nj] = (step + 1) * s;
					bvis[ni][nj] = true;
				}
			}
		}
		/* debug(steps); */
		q = queue<array<ll, 3>> ();
		if(steps[start.ff][start.ss] != 0) q.push({start.ff, start.ss, 0LL});
		mvis[start.ff][start.ss] = true;
		ll minutes = -1; // -1 means unreachability
		while(!q.empty()) {
			array<ll, 3> t = q.front(); q.pop();
			int x = t[0], y = t[1], step = t[2];
			if(v[x][y] == 'D') {
				minutes = step;
				break;
			}

			for(int i = 0; i < 4; ++i) {
				int ni = x + dx[i], nj = y + dy[i];
				if(mvalid(ni, nj) && !mvis[ni][nj] && steps[ni][nj] > (step + 1)) {
					mvis[ni][nj] = true;
					q.push({ni, nj, step + 1});
				}
			}
		}

		if(minutes != -1) {
			ans = mid; si = mid + 1;
		}
		else ei = mid - 1;
	}
	cout << ans;
	return 0;
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    bool test = false;
	int TET = 1;
    if(test) cin >> TET;
    cout << fixed << setprecision(6);
    for (int i = 1; i <= TET; i++) {
		#ifdef LOCAL
        	cout << "##################" << '\n';
		#endif

        if (solve()) {
            break;
        }
        cout << '\n';
    }
	#ifdef LOCAL
    	cout << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
	#endif
	return 0;
}
// -> Keep It Simple Stupid!

• Subtask 1: 64 / 100