Submission #597616

#	Time	Username	Problem	Language	Result	Execution time	Memory
597616		l_reho	Mecho (IOI09_mecho)	C++14	100 / 100	205 ms	4544 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int N, S;

vector<string> V;
vector<vector<int>> P;

int dirs[4][2] = {{1, 0},{0, 1},{-1, 0},{0, -1}};

struct info{
	int r, c, d;
	info(){}
	
	info(int _r, int _c, int _d): r(_r), c(_c), d(_d) {}
};

void precompute(vector<pair<int, int>> starts){
	
	queue<info> q;
	
	for(int i = 0; i < (int)starts.size(); i++){
		q.push(info(starts[i].first, starts[i].second, 0));
		P[starts[i].first][starts[i].second] = 0;
	}
	
	while(!q.empty()){
		info curr = q.front();
		q.pop();
		
		int r = curr.r;
		int c = curr.c;
		int depth = curr.d;
		
		for(int i = 0; i < 4; i++){
			int nr = r + dirs[i][0];
			int nc = c + dirs[i][1];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= N || (V[nr][nc] != 'G' && V[nr][nc] != 'M') || P[nr][nc] != INT_MAX) continue;
			 
			P[nr][nc] = depth+1;
			
			q.push(info(nr, nc, depth+1));
			
		}
		
	}
	
	
}

bool solver(int r, int c, int dr, int dc, int l){
	
	queue<info> q;
	
	q.push(info(r, c, l+1));	
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	
	while(!q.empty()){
		info curr = q.front();
		q.pop();
		
		int r = curr.r;
		int c = curr.c;
		int depth = curr.d;
			
		// cout<<"DEBUG-->"<<l<<" "<<r<<" "<<c<<endl;
		visited[r][c] = true;
		
		for(int i = 0; i < 4; i++){
			int nr = r + dirs[i][0];
			int nc = c + dirs[i][1];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= N || (V[nr][nc] != 'G' && V[nr][nc] != 'D') || visited[nr][nc] || P[nr][nc] <= (l + (int)((depth-l)/S))) continue;
	
			visited[nr][nc] = true;
	
			q.push(info(nr, nc, depth+1));
				
		}
		
	}
	
		
	return visited[dr][dc];
}

void solve(){
	cin>>N>>S;
	
	V.assign(N, "");
	P.assign(N, vector<int>(N, INT_MAX));
	
	vector<pair<int, int>> starts;
	int sr, sc, dr, dc;
	for(int i = 0; i < N; i++){
		cin>>V[i];
		for(int j = 0; j < N; j++) 
			if(V[i][j] == 'H') starts.push_back({i, j});
			else if(V[i][j] == 'M') sr = i, sc = j;
			else if(V[i][j] == 'D') dr = i, dc = j;
			
	}
	
	precompute(starts);

	int low = 0;
	int high = P[sr][sc];
	int ans = -1;

	while(low < high){
		int mid = low + (high - low)/2;


		if(solver(sr, sc, dr, dc, mid)){
			ans = mid;
			low = mid+1;
		}else high = mid;
		
	}
	
	cout<<ans<<endl;
	
}

int main(){
	solve();
}

Compilation message (stderr)

mecho.cpp: In function 'void solve()':
mecho.cpp:117:12: warning: 'dr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |   if(solver(sr, sc, dr, dc, mid)){
      |      ~~~~~~^~~~~~~~~~~~~~~~~~~~~
mecho.cpp:110:21: warning: 'sc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |  int high = P[sr][sc];
      |                     ^
mecho.cpp:110:17: warning: 'sr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |  int high = P[sr][sc];
      |                 ^
mecho.cpp:117:12: warning: 'dc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |   if(solver(sr, sc, dr, dc, mid)){
      |      ~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100