Submission #341035

#	Time	Username	Problem	Language	Result	Execution time	Memory
341035		peuch	Mecho (IOI09_mecho)	C++17	100 / 100	281 ms	17388 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
 
const int MAXN = 1010;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
 
int n;
long long s;
int hx, hy;
int mx, my;
char grid[MAXN][MAXN];
long long beeDist[MAXN][MAXN];
int marc[MAXN][MAXN];
long long dist[MAXN][MAXN];
 
void preCalc();
bool test(long long temp);
long long bb();
 
int main(){
	scanf("%d %lld", &n, &s);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			scanf(" %c", &grid[i][j]);
			if(grid[i][j] == 'D') hx = i, hy = j;
			if(grid[i][j] == 'M') mx = i, my = j;
		}
	}
	preCalc();
	printf("%d\n", bb());
}
 
void preCalc(){
	queue<int> fila;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(grid[i][j] != 'H') beeDist[i][j] = 1e18;
			else{
				marc[i][j] = 1;
				fila.push(i);
				fila.push(j);
			}
		}
	}
	while(!fila.empty()){
		int curx = fila.front();
		fila.pop();
		int cury = fila.front();
		fila.pop();
		for(int i = 0; i < 4; i++){
			int vizx = curx + dx[i];
			int vizy = cury + dy[i];
			if(vizx <= 0 || vizx > n) continue;
			if(vizy <= 0 || vizy > n) continue;
			if(grid[vizx][vizy] == 'T') continue;
			if(grid[vizx][vizy] == 'D') continue;
			if(marc[vizx][vizy]) continue;
			marc[vizx][vizy] = 1;
			beeDist[vizx][vizy] = beeDist[curx][cury] + s;
			fila.push(vizx);
			fila.push(vizy);
		}
	}
}
 
bool test(long long temp){
	queue<int> fila;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			marc[i][j] = 0;
			dist[i][j] = 0;
		}
	}
	fila.push(mx);
	fila.push(my);
	marc[mx][my] = 1;
	dist[mx][my] = temp * s;
	if(dist[mx][my] >= beeDist[mx][my]) return 0;
	while(!fila.empty()){
		int curx = fila.front();
		fila.pop();
		int cury = fila.front();
		fila.pop();
		for(int i = 0; i < 4; i++){
			int vizx = curx + dx[i];
			int vizy = cury + dy[i];
			if(vizx <= 0 || vizx > n) continue;
			if(vizy <= 0 || vizy > n) continue;
			if(grid[vizx][vizy] == 'T') continue;
			if(dist[curx][cury] + 1 >= beeDist[vizx][vizy]) continue;
			if(marc[vizx][vizy]) continue;
			marc[vizx][vizy] = 1;
			dist[vizx][vizy] = dist[curx][cury] + 1;
			fila.push(vizx);
			fila.push(vizy);
		}
	}
	return marc[hx][hy];
}
 
long long bb(){
	long long ini = 0, fim = 2e8 + 10;
	if(!test(ini)) return -1;
	while(ini != fim){
		long long mid = (ini + fim) >> 1;
		if(ini == fim - 1) mid = fim;
		if(test(mid)) ini = mid;
		else fim = mid - 1;
	}
	return ini;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:32:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   32 |  printf("%d\n", bb());
      |          ~^     ~~~~
      |           |       |
      |           int     long long int
      |          %lld
mecho.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |  scanf("%d %lld", &n, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
mecho.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |    scanf(" %c", &grid[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100