Submission #891842

#	Time	Username	Problem	Language	Result	Execution time	Memory
891842		bashNewbie	Mecho (IOI09_mecho)	C++17	100 / 100	205 ms	9520 KiB

mecho

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

#define fast_io ios::sync_with_stdio(0), cin.tie(0)
#define pb push_back
template <typename T> using vt = vector<T>;
using vi = vt<int>;
using vs = vt<string>;

const int inf = 0x3f3f3f3f;

int main() {
	fast_io;

	int N, n, d; cin >> N >> d, n = N*N;
	vs s(N); int srt, fin; vi hiv;
	for(int i = 0; i < N; i++) {
		cin >> s[i];
		for(int j = 0; j < N; j++) {
			int x = i*N+j;
			if(s[i][j] == 'M') srt = x;
			if(s[i][j] == 'D') fin = x;
			if(s[i][j] == 'H') hiv.pb(x); 
		}
	}
	queue<int> q; vi hdis(n, inf), dis; int f;

	auto put = [&] (int x, int y, int c) {
		if(c == 0) {
			if(hdis[y] < inf) return;
			int a = y/N, b = y-a*N;
			if(s[a][b] == 'T' || s[a][b] == 'D') return;
			q.push(y), hdis[y] = hdis[x]+1;
		} else
		if(c == 1) {
			if(dis[y] < inf) return;
			if(y == fin) {
				q.push(y), dis[y] = 0;
				return;
			}
			int a = y/N, b = y-a*N;
			if(s[a][b] == 'T') return;
			
			int tim = f+(dis[x]+1)/d;
			if(hdis[y] <= tim) return;
			q.push(y), dis[y] = dis[x]+1;
		}
	};
	auto bfs = [&] (int c) {
		while(!q.empty()) {
			int x = q.front(); q.pop();
			if(x == fin) {
				while(!q.empty()) q.pop();
				return;
			}

			if(x%N > 0) put(x, x-1, c);
			if(x%N<N-1) put(x, x+1, c);
			if(x/N > 0) put(x, x-N, c);
			if(x/N<N-1) put(x, x+N, c);
		}
	};

	for(int x: hiv) q.push(x), hdis[x] = 0;
	bfs(0);

	auto poss = [&] (int m) {
		if(m >= hdis[srt]) return 0;

		q.push(srt), dis = vi(n, inf), dis[srt] = 0, f = m;
		bfs(1);
		return dis[fin] < inf? 1: 0;
	};
	
	int l = -1, r = inf, m;
	while(l < r) {
		m = l+r+1 >> 1;
		if(poss(m)) l = m; else
		r = m-1;
	}
	cout << l << "\n";
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:81:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   m = l+r+1 >> 1;
      |       ~~~^~

• Subtask 1: 100 / 100