제출 #293929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293929		kshitij_sodani	Mecho (IOI09_mecho)	C++14	54 / 100	275 ms	8840 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back

typedef long long llo;
#define endl '\n'



int n,s;
queue<pair<int,int>> ss;
int dist[801][801];
int it[801][801];
vector<int> x={1,-1,0,0};
vector<int> y={0,0,1,-1};
int dd[801][801];

pair<int,int> aa;
pair<int,int> bb;

bool check(int mid){
	queue<pair<int,int>> tt;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dd[i][j]=-1;
		}
	}
	dd[aa.a][aa.b]=0;
	tt.push({aa.a,aa.b});
	while(tt.size()){
		pair<int,int> no=tt.front();
		tt.pop();
		//if(dd[no.a][no.b])
		for(int i=0;i<4;i++){
			int xx=no.a+x[i];
			int yy=no.b+y[i];
			if(xx<0 or xx>=n or yy<0 or yy>=n){
				continue;
			}
			if(it[xx][yy]==0){
				continue;
			}
			if(dd[xx][yy]==-1){
				if(dist[xx][yy]!=-1){
					if(dist[xx][yy]<=mid-1+(dd[no.a][no.b]+1+s-1)/s){
					
						continue;
					}
				}

				dd[xx][yy]=dd[no.a][no.b]+1;
				//cout<<xx<<":"<<yy<<":"<<dd[xx][yy]<<endl;
				tt.push({xx,yy});
			}
		}
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout<<dd[i][j]<<",";
		}
		cout<<endl;
	}
	cout<<mid<<":"<<dd[bb.a][bb.b]<<endl;*/
	return dd[bb.a][bb.b]!=-1;

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>s;
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dist[i][j]=-1;
			char s;
			cin>>s;
			it[i][j]=1;
			if(s=='T'){
				it[i][j]=0;
			}
			else if(s=='G'){
			}
			else if(s=='M'){
				aa={i,j};
			}
			else if(s=='D'){
				it[i][j]=0;
				bb={i,j};
			}
			else if(s=='H'){
				ss.push({i,j});
				dist[i][j]=0;
			}
		}
	}
	while(ss.size()){
		pair<int,int> no=ss.front();
		ss.pop();
		for(int i=0;i<4;i++){
			int xx=no.a+x[i];
			int yy=no.b+y[i];
			if(xx<0 or xx>=n or yy<0 or yy>=n){
				continue;
			}
			if(it[xx][yy]==0){
				continue;
			}
			if(dist[xx][yy]==-1){
				dist[xx][yy]=dist[no.a][no.b]+1;
				ss.push({xx,yy});
			}
		}
	}
	int low=0;
	int high=dist[aa.a][aa.b]-1;
	it[bb.a][bb.b]=1;
	if(check(low)==false){
		cout<<-1<<endl;
	}
	else{
		while(low<high-1){
			int mid=(low+high)/2;
			if(check(mid)){
				low=mid;
			}
			else{
				high=mid;
			}
		}
		int ans=low;
		if(check(high)){
			ans=max(ans,high);
		}
		cout<<ans<<endl;
	}




	return 0;
}

• Subtask 1: 54 / 100