Submission #1109985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109985		dsyz	Mecho (IOI09_mecho)	C++17	38 / 100	146 ms	11604 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,S;
	cin>>N>>S;
	pair<ll,ll> start = {-1,-1};
	pair<ll,ll> end = {-1,-1};
	char arr[N][N];
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < N;j++){
			cin>>arr[i][j];
			if(arr[i][j] == 'M') start = {i,j};
			if(arr[i][j] == 'D') end = {i,j};
		}
	}
	queue<pair<ll,ll> > q;
	ll fromhive[N][N];
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < N;j++){
			fromhive[i][j] = 1e18;
			if(arr[i][j] == 'H'){
				q.push({i,j});
				fromhive[i][j] = 0;
			}
		}
	}
	int Hy[] = {0,0,-1,1};
	int Wx[] = {-1,1,0,0};
	while(!q.empty()){
		ll y = q.front().first;
		ll x = q.front().second;
		q.pop();
		for(ll i = 0;i < 4;i++){
			ll a = y + Hy[i];
			ll b = x + Wx[i];
			if(a < 0 || a >= N || b < 0 || b >= N || arr[a][b] == 'T' || arr[a][b] == 'D'){
				continue;	
			}
			if(fromhive[a][b] == 1e18){
				q.push({a,b});
				fromhive[a][b] = fromhive[y][x] + 1;
			}
		}
	}
	ll high = 1e6 + 5;
	ll low = -1;
	while(high - low > 1){
		ll mid = (high + low) / 2;
		ll dist[N][N];
		memset(dist,-1,sizeof(dist));
		q.push(start);
		dist[start.first][start.second] = 0;
		ll time = max(0ll,mid);
		ll add = 0;
		while(true){
			queue<pair<ll,ll> > newq;
			while(!q.empty()){
				ll y = q.front().first;
				ll x = q.front().second;
				q.pop();
				if(dist[y][x] == S + add){
					for(ll ind = 0;ind < 4;ind++){
						ll aa = y + Hy[ind];
						ll bb = x + Wx[ind];
						if(aa < 0 || aa >= N || bb < 0 || bb >= N || arr[aa][bb] == 'T'){
							continue;
						}
						if(dist[aa][bb] == -1 && time + 1 < fromhive[aa][bb]){
							newq.push({y,x});
							break;
						}
					}
				}
				for(ll i = 0;i < 4;i++){
					ll a = y + Hy[i];
					ll b = x + Wx[i];
					if(a < 0 || a >= N || b < 0 || b >= N || arr[a][b] == 'T'){
						continue;	
					}
					if(dist[a][b] == -1 && dist[y][x] + 1 <= S + add && time < fromhive[a][b]){
						dist[a][b] = dist[y][x] + 1;
						q.push({a,b});
					}
				}
			}
			time++;
			add += S;
			while(!newq.empty()){
				q.push(newq.front());
				newq.pop();
			}
			if(q.empty()){
				break;
			}
		}
		if(dist[end.first][end.second] == -1){
			high = mid;
		}else{
			low = mid;
		}
	}
	cout<<low<<'\n';
}

• Subtask 1: 38 / 100