Submission #941726

#	Time	Username	Problem	Language	Result	Execution time	Memory
941726		RavenHead	Mecho (IOI09_mecho)	C++17	70 / 100	185 ms	11708 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define EB emplace_back
#define all(x) std::begin(x), std::end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for(long long i = a; i < (b); ++i)
#define endl '\n'
#define debarr(a, n) cerr << #a << " : ";for(int i = 0; i < n; i++) cerr << a[i] << " "; cerr << endl;
#define debmat(mat, row, col) cerr << #mat << " :\n";for(int i = 0; i < row; i++) {for(int j = 0; j < col; j++) cerr << mat[i][j] << " ";cerr << endl;}
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const unordered_set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const unordered_map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}

typedef long long lli;
typedef pair<lli, lli> ii;    typedef vector<lli> vi;
typedef vector<ii> vii;       typedef vector<vi> graph;
bool ckmax(auto &a, auto const& b) {return b > a ? a = b, 1 : 0;}
bool ckmin(auto &a, auto const& b) {return b < a ? a = b, 1 : 0;}

int const MOD = 1000000007;

void pre() {

}

void solve() {
	lli n, s;
	cin >> n >> s;
	vector<string> arr(n);
	rep(i, 0, n) {
		cin >> arr[i];
	}
	ii mecho, home;
	rep(i, 0, n)rep(j, 0, n) {
		if (arr[i][j] == 'M') {
			mecho = {i, j};
		}
		else if (arr[i][j] == 'D') {
			home = {i, j};
		}
	}

	// checks function
	auto checks = [&](lli xx, lli yy)->bool{
		if (xx >= 0 && xx < n && yy >= 0 && yy < n && (arr[xx][yy] == 'G' || arr[xx][yy] == 'D'))return true;
		return false;
	};

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

	graph dis(n, vi(n, 1e9));
	queue<ii> q;
	rep(i, 0, n)rep(j, 0, n)if (arr[i][j] == 'H') {
		q.push({i, j});
		dis[i][j] = 0;
	}
	while (!q.empty()) {
		auto nn = q.front(); q.pop();
		rep(dir, 0, 4) {
			lli xx = nn.F + dx[dir];
			lli yy = nn.S + dy[dir];
			if (checks(xx, yy)) {
				if (dis[xx][yy] > dis[nn.F][nn.S] + 1) {
					dis[xx][yy] = dis[nn.F][nn.S] + 1;
					q.push({xx, yy});
				}
			}
		}
	}

	// check function
	auto check = [&](lli mid)->bool{
		graph d(n, vi(n, 1e9));
		d[mecho.F][mecho.S] = 0;
		q.push(mecho);
		while (!q.empty()) {
			auto nn = q.front(); q.pop();
			rep(dir, 0, 4) {
				lli xx = nn.F + dx[dir];
				lli yy = nn.S + dy[dir];
				if (xx >= 0 && xx < n && yy >= 0 && yy < n && (arr[xx][yy] == 'G' || arr[xx][yy] == 'D')) {
					if (d[xx][yy] > d[nn.F][nn.S] + 1) {
						lli val = d[nn.F][nn.S] + 1;
						if (dis[xx][yy] >= mid + (val + s - 1) / s) {
							d[xx][yy] = val;
							q.push({xx, yy});
						}
					}
				}
			}
		}
		return mid + (d[home.F][home.S] + s - 1) / s < dis[home.F][home.S];
	};

	lli low = 0;
	lli high = 1e9;
	lli ans = -1;
	while (low <= high) {
		lli mid = (high + low) / 2;
		if (check(mid)) {
			ans = mid;
			low = mid + 1;
		} else high = mid - 1;
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	pre();
	int T = 1;
	while (T--)
		solve();
	return 0;
}

Compilation message (stderr)

mecho.cpp:27:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 | bool ckmax(auto &a, auto const& b) {return b > a ? a = b, 1 : 0;}
      |            ^~~~
mecho.cpp:27:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 | bool ckmax(auto &a, auto const& b) {return b > a ? a = b, 1 : 0;}
      |                     ^~~~
mecho.cpp:28:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 | bool ckmin(auto &a, auto const& b) {return b < a ? a = b, 1 : 0;}
      |            ^~~~
mecho.cpp:28:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 | bool ckmin(auto &a, auto const& b) {return b < a ? a = b, 1 : 0;}
      |                     ^~~~

• Subtask 1: 70 / 100