Submission #501333

#	Time	Username	Problem	Language	Result	Execution time	Memory
501333		sidon	Mecho (IOI09_mecho)	C++17	38 / 100	746 ms	3848 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define c(X, Y) (X * N + Y)
 
const int INF = 1e8;
 
const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};
 
int N, S, d[1<<20], ans = -1, e, r;
 
string g[1<<10];
 
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> S;
 
	for(int i = 0; i < N; i++)
		cin >> g[i];
 
	for(int b = r = 20; --b >= 0; ) {
		ans += 1 << b;
 
		fill(d, d + N * N, INF);
		queue<int> p, q;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(g[i][j] == 'D')
					e = c(i, j);
				if(g[i][j] == 'M')
					d[c(i, j)] = 0, q.push(c(i, j));
				if(g[i][j] == 'H')
					d[c(i, j)] = -1, p.push(c(i, j));
			}
		}
 
		int ext = ans;
 
		while(!empty(q)) {
			int lim = ext-- > 0 ? 0 : d[q.front()] + S;
 
			for(int t : {1, -1}) {
				while(!empty(q) && (t * d[q.front()]) < lim) {
					int k = q.front(), i = k / N, j = k % N; q.pop();
 
					for(int s = 0; s < 4; s++) {
						int x = i + di[s], y = j + dj[s], z = x * N + y;
 
						if(min(x, y) < 0 || max(x, y) >= N || d[z] != INF) continue;
						if(g[x][y] & 1 || (t > 0 && z == e))
							d[z] = d[k] + t, q.push(z);
					}
				}
				swap(p, q);
				if(!empty(q)) lim = 1 - d[q.front()];
			}
		}
 
		if(d[e] == INF)
			ans -= 1 << b;
	}
	cout << ans;
}

• Subtask 1: 38 / 100