Submission #519415

#	Time	Username	Problem	Language	Result	Execution time	Memory
519415		MODDI	Mecho (IOI09_mecho)	C++14	49 / 100	222 ms	6420 KiB

mecho

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, s,sx, sy, ex, ey;
const int Nmax = 1000;
char mat[Nmax][Nmax];
int dist[Nmax][Nmax];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pii> hives;
class state{
	public:
		int x;
		int y;
		int steps_made;
		int cur_minute;
};
bool in_range(int i, int j){
	if(i >= 0 && j >= 0 && i < n && j < n)
		return true;
	return false;
}
void calculate_dist(){
	queue<vector<pii> > q;
	q.push(hives);
	while(!q.empty()){
		vector<pii> current = q.front(); q.pop();
		vector<pii> next_current;
		for(int i = 0; i < current.size(); i++){
			int x = current[i].first, y = current[i].second;
			for(int dir = 0; dir < 4; dir++){
				int nx = x + dx[dir], ny = y + dy[dir];
				if(in_range(nx, ny) && mat[nx][ny] != 'T' && dist[nx][ny] == -1){
					dist[nx][ny] = 1 + dist[x][y];
					next_current.pb(mp(nx,ny));
				}
			}
		}
		if(next_current.size() > 0)
			q.push(next_current);
	}
}
bool solve(int minutes){
	queue<state> q;
	q.push({sx,sy,0,minutes+1});
	bool finished = false;
	bool vis[801][801];
	memset(vis, false, sizeof(vis));
	vis[sx][sy] = true;
	while(!q.empty()){
		state current = q.front(); q.pop();
		int x = current.x, y = current.y, steps_made = current.steps_made, cur_minute = current.cur_minute;
		//cout<<x<<" "<<y<<" "<<steps_made<<" "<<cur_minute<<endl;
		if(steps_made == s){
			steps_made = 0;
			cur_minute++;
		}
			
		for(int dir = 0; dir < 4; dir++){
			int nx = x + dx[dir], ny = y + dy[dir];
			//cout<<dist[nx][ny]<<" "<<cur_minute<<endl;
			if(in_range(nx,ny) && mat[nx][ny] != 'T' &&  !vis[nx][ny] && dist[nx][ny] >= cur_minute){
				if(dist[nx][ny] == cur_minute && steps_made + 1 == s)
					continue;
				if(nx == ex && ny == ey){
					finished = true;
					break;
				}
				vis[nx][ny] = true;
				q.push({nx, ny, steps_made + 1, cur_minute});
			}
		}
		if(finished)
			break;
	}
	return finished;
}
int main(){
	cin>>n>>s;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin>>mat[i][j];
			if(mat[i][j] == 'M')
				sx = i, sy = j;
			if(mat[i][j] == 'D')
				ex = i, ey = j;
			if(mat[i][j] == 'H')
				hives.pb(mp(i,j));
		}
	}
	memset(dist, -1, sizeof(dist));
	for(int i = 0; i < hives.size(); i++)
		dist[hives[i].first][hives[i].second] = 0;
		
	calculate_dist(); 
	int l = 0, r = 10000, solution=-1;
	while(l <= r){
		int mid = (l + r) / 2;
		bool sol = solve(mid);
		if(sol){
			solution = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout<<solution<<endl;
}

Compilation message (stderr)

mecho.cpp: In function 'void calculate_dist()':
mecho.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i = 0; i < current.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 0; i < hives.size(); i++)
      |                 ~~^~~~~~~~~~~~~~

• Subtask 1: 49 / 100