제출 #1109952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1109952		dsyz	Mecho (IOI09_mecho)	C++17	13 / 100	69 ms	12200 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];
	memset(fromhive,-1,sizeof(fromhive));
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < N;j++){
			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] == 'H'){
				continue;	
			}
			if(fromhive[a][b] == -1){
				q.push({a,b});
				fromhive[a][b] = fromhive[y][x] + 1;
			}
		}
	}
	/*cout<<"FROMHIVE: "<<'\n';
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < N;j++){
			cout<<fromhive[i][j]<<" ";	
		}
		cout<<'\n';
	}*/
	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);
		//cout<<"MID: "<<mid<<'\n';
		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();
				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] == 'H'){
						continue;	
					}
					if(dist[a][b] == -1 && dist[y][x] + 1 <= S + add && time < fromhive[a][b]){
						dist[a][b] = dist[y][x] + 1;
						if(dist[a][b] == S){
							for(ll ind = 0;ind < 4;ind++){
								ll aa = a + Hy[ind];
								ll bb = b + Wx[ind];
								if(aa < 0 || aa >= N || bb < 0 || bb >= N || arr[aa][bb] == 'T' || arr[aa][bb] == 'H'){
									continue;
								}
								if(dist[aa][bb] == -1 && time + 1 < fromhive[aa][bb]){
									newq.push({a,b});
									break;
								}
							}
						}else{
							q.push({a,b});
						}
					}
				}
			}
			//cout<<"CURTIME: "<<time<<'\n';
			/*if(mid == 2){
				cout<<"DIST: "<<'\n';
				for(ll ii = 0;ii < N;ii++){
					for(ll jj = 0;jj < N;jj++){
						cout<<dist[ii][jj]<<" ";
					}
					cout<<'\n';
				}
				cout<<'\n';
			}*/
			time++;
			add += S;
			while(!newq.empty()){
				q.push(newq.front());
				//if(mid == 2) cout<<"NEWQ: "<<newq.front().first<<" "<<newq.front().second<<'\n';
				newq.pop();
			}
			if(q.empty()){
				break;
			}
		}
		if(dist[end.first][end.second] == -1){
			high = mid;
		}else{
			low = mid;
		}
	}
	cout<<low<<'\n';
}

• Subtask 1: 13 / 100