Submission #731039

#	Time	Username	Problem	Language	Result	Execution time	Memory
731039		CutSandstone	Mecho (IOI09_mecho)	C++17	100 / 100	313 ms	11532 KiB

mecho

#include <bits/stdc++.h>
#define f first
#define s second
using ll = long long;
using namespace std;
const int inf = 1<<30;
int bees[800][800];
bool go[800][800];
bool vis[800][800];
int bfs[640000][3];
int p1, p2, len;
int ra, rb, rc;
pair<int, int> st, en;
pair<int, int> d4[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int N, S;
void push(int a, int b, int c){
	bfs[p2][0] = a;
	bfs[p2][1] = b;
	bfs[p2][2] = c;
	p2++;
	if(p2 == 640000) p1 = 0;
	len++;
}
void poll(){
	ra = bfs[p1][0];
	rb = bfs[p1][1];
	rc = bfs[p1][2];
	p1++;
	if(p1 == 640000) p1 = 0;
	len--;
}
void reset(int t){
	p1 = p2 = 0;
	push(st.f, st.s, 0);
	vis[st.f][st.s] = 0;
	while(len) {
		poll();
		for(pair<int, int> a: d4) {
			int na = ra+a.f, nb = rb+a.s;
			if(na >= 0 && na < N && nb >= 0 && nb < N && 
			go[na][nb] && (rc+1)/S < bees[na][nb]-t && vis[na][nb]) {
				push(na, nb, rc+1);
				vis[na][nb] = 0;
			}
		}
	}
}
bool works(int t){
	p1 = p2 = 0;
	push(st.f, st.s, 0);
	vis[st.f][st.s] = 1;
	while(len) {
		poll();
		for(pair<int, int> a: d4) {
			int na = ra+a.f, nb = rb+a.s;
			if(na >= 0 && na < N && nb >= 0 && nb < N && 
			go[na][nb] && (rc+1)/S < bees[na][nb]-t && !vis[na][nb]) {
				if(na == en.f && nb == en.s){
					reset(t);
					return 1;
				}
				push(na, nb, rc+1);
				vis[na][nb] = 1;
			}
		}
	}
	reset(t);
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	p1 = p2 = len = 0;
	cin >> N >> S;
	for(int i = 0; i<N; i++) for(int j = 0; j<N; j++) bees[i][j] = inf;
	for(int i = 0; i<N; i++) {
	    string c; cin >> c;
		for(int j = 0; j<N; j++) {
			go[i][j] = c[j] != 'T';
			if(c[j] == 'M') st = {i, j};
			if(c[j] == 'D') en = {i, j};
			if(c[j] == 'H') {
				push(i, j, 0);
				bees[i][j] = 0;
			}
		}
	}
	while(len) {
	    poll();
		int c = bees[ra][rb];
		for(pair<int, int> a: d4) {
		    pair<int, int> next = {ra+a.f, rb+a.s};
			if(next.f >= 0 && next.s >= 0 && next.f < N && next.s < N && 
			go[next.f][next.s] && bees[next.f][next.s] == inf && (next.f != en.f || next.s != en.s)) {
				bees[next.f][next.s] = c+1;
				push(next.f, next.s, 0);
			}
		}
	}
	int lo = -1, hi = bees[st.f][st.s]-1;
	while (lo < hi) {
		int mid = (lo+hi+1)>>1;
		if (works(mid)) lo = mid;
		else hi = mid-1;
	}
	cout << lo;
}

• Subtask 1: 100 / 100