Submission #309481

#	Time	Username	Problem	Language	Result	Execution time	Memory
309481		sofapuden	Mecho (IOI09_mecho)	C++14	100 / 100	476 ms	6544 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

int n, k;
bool ok = 0;
int mid;

pair<int,int> sta, en;

vector<string> G;
vector<vector<int>> V;
vector<vector<int>> vis;

queue<pair<pair<int,int>,int>> Q, Q2;

void search2(pair<pair<int,int>,int> now){
	if(vis[now.f.f][now.f.s])return;
	vis[now.f.f][now.f.s] = 1;
	if(now.f.f != n-1){
		if(V[now.f.f+1][now.f.s] > (now.s+1)/k+mid){
			Q2.push({{now.f.f+1,now.f.s},now.s+1});
		}
	}
	if(now.f.s != n-1){
		if(V[now.f.f][now.f.s+1] > (now.s+1)/k+mid){
			Q2.push({{now.f.f,now.f.s+1},now.s+1});
		}
	}
	
	if(now.f.f != 0){
		if(V[now.f.f-1][now.f.s] > (now.s+1)/k+mid){
			Q2.push({{now.f.f-1,now.f.s},now.s+1});
		}
	}
	
	if(now.f.s != 0){
		if(V[now.f.f][now.f.s-1] > (now.s+1)/k+mid){
			Q2.push({{now.f.f,now.f.s-1},now.s+1});
		}
	}

			
}
void search(pair<pair<int,int>,int> now){
	if(now.f.f < 0 || now.f.s < 0 || now.f.f >= n || now.f.s >= n)return;
	if(V[now.f.f][now.f.s] != -1)return;
	V[now.f.f][now.f.s] = now.s;
	Q.push({{now.f.f-1,now.f.s},now.s+1});
	Q.push({{now.f.f+1,now.f.s},now.s+1});
	Q.push({{now.f.f,now.f.s-1},now.s+1});
	Q.push({{now.f.f,now.f.s+1},now.s+1});
}

int main(){ 
	cin >> n >> k;
	G.resize(n);
	V.resize(n, vector<int> (n,-1));
	
	for(auto &x : G)cin >> x;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(G[i][j] == 'T')V[i][j] = -2;
			if(G[i][j] == 'M')sta = {i,j};
			if(G[i][j] == 'D'){en = {i,j};V[i][j] = 1000000;}
			if(G[i][j] == 'H')Q.push({{i,j},0});
		}
	}
	while(!Q.empty()){
		auto x = Q.front();
		Q.pop();
		search(x);
	}
	//for(int i = 0; i < n; ++i){
		//for(int j = 0; j < n; ++j){
			//cout << V[i][j] << " ";
		//}
		//cout << "\n";
	//}
	int best = -1;
	int hi = V[sta.f][sta.s]-1, lo = 0;
	while(lo <= hi){
		mid = (hi+lo)/2;
		vis.clear();
		vis.resize(n, vector<int> (n, 0));
		Q2.push({sta,0});
		ok = 0;
		while(!Q2.empty()){
			auto x = Q2.front();
			Q2.pop();
			if(x.f == en){ok = 1;break;}
			search2(x);
		}
		Q2 = queue<pair<pair<int,int>,int>>();
		if(ok){lo = mid+1;best = mid;}
		else hi = mid-1;
	}
	cout << best << "\n";

}
	
	
	

• Subtask 1: 100 / 100