제출 #553461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553461		SharpEdged	Mecho (IOI09_mecho)	C++17	100 / 100	195 ms	6356 KiB

mecho

#include <bits/stdc++.h>
 
using namespace std;
 
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define LSB(x) ((x) & -(x))
#define sz(x) (int)(x.size())
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[DEBUG] "<<__func__<<": "<<__LINE__<<", [" << #x << "] = ["; _print(x);
#else
#define dbg(x...)
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    
    size_t operator()(string x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        uint64_t res = 0;
        for (int i = 0; i < sz(x); i++){
			res ^= x[i] + FIXED_RANDOM;
			res = splitmix64(res);
		}
        return res;
    }
};

const ll MOD = 1e9 + 7;
const ll INFLL = 1e18 + 5;
const int INF = 1e9 + 5;

char nl = '\n';

ll modPow(ll n, ll k){
	if (k == 0) return 1;
	ll res = modPow(n, k / 2);
	res = res * res % MOD;
	if (k & 1) return res * n % MOD;
	return res;
}

const int mxN = 51;

int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

void TestCase(){
	int n, m;
	cin >> n >> m;
	vector<string> grid(n);
	vector<vector<int>> bad(n, vector<int>(n, INF));
	vector<vector<int>> dist(n, vector<int>(n, INF));
	pair<int, int> s, e;
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++){
		cin >> grid[i];
		for (int j = 0; j < n; j++){
			if (grid[i][j] == 'H') {
				bad[i][j] = 0;
				q.push({i, j});
			} else if (grid[i][j] == 'M'){
				s = {i, j};
			} else if (grid[i][j] == 'D'){
				e = {i, j};
			}
		}
	}
	auto inside = [&](int i, int j) -> bool { return i >= 0 && i < n && j >= 0 && j < n; };
	while (!q.empty()){
		auto now = q.front(); q.pop();
		for (int i = 0; i < 4; i++){
			int nr = now.f + dr[i];
			int nc = now.s + dc[i];
			if (!inside(nr, nc) || (grid[nr][nc] != 'G' && grid[nr][nc] != 'M')) continue;
			if (bad[nr][nc] == INF){
				bad[nr][nc] = bad[now.f][now.s] + 1;
				q.push({nr, nc});
			}
		}
	}
	auto check = [&](int mins) -> bool {
		if (bad[s.f][s.s] <= mins) return 0;
		dist.assign(n, vector<int>(n, INF));
		q.push(s);
		dist[s.f][s.s] = 0;
		while (!q.empty()){
			auto now = q.front(); q.pop();
			int elap = mins + (dist[now.f][now.s] + 1) / m;
			for (int i = 0; i < 4; i++){
				int nr = now.f + dr[i];
				int nc = now.s + dc[i];
				if (!inside(nr, nc) || (grid[nr][nc] != 'G' && grid[nr][nc] != 'D') || elap >= bad[nr][nc]) continue;
				if (dist[nr][nc] == INF){
					dist[nr][nc] = dist[now.f][now.s] + 1;
					q.push({nr, nc});
				}
			}
		}
		return dist[e.f][e.s] != INF;
	};
	
	int lo = 0, hi = 1e6;
	int ans = -1;
	while (lo <= hi){
		int mid = (lo + hi) / 2;
		if (check(mid)){
			lo = mid+1;
			ans = mid;
		} else {
			hi = mid-1;
		}
	}
	cout << ans << nl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T = 1;
	//cin >> T;
	while (T--){
		TestCase();
	}
	return 0;
}

• Subtask 1: 100 / 100