Submission #945000

#	Time	Username	Problem	Language	Result	Execution time	Memory
945000		sano	Mecho (IOI09_mecho)	C++17	100 / 100	168 ms	6664 KiB

mecho

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>
#include<algorithm>
#define For(i, n) for(int i = 0; i < n; i++)
#define ffor(i, a, n) for(int i = a; i < n; i++)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pairs pair<int, int>
#define NEK 1000000000

using namespace std;

vec<pairs> r = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void BFS(queue<pairs>&q, vec<vec<char>>&p, vec<vec<int>>&d) {
	while (!q.empty()) {
		pairs x = q.front(); q.pop();
		For(i, 4) {
			pairs t = { x.ff + r[i].ff, x.ss + r[i].ss };
			if (t.ff < 0 || t.ss < 0 || t.ff >= p.size() || t.ss >= p.size()) continue;
			if (p[t.ff][t.ss] == 'T' || p[t.ff][t.ss] == 'D') continue;
			if (d[t.ff][t.ss] != -1) continue;
			d[t.ff][t.ss] = d[x.ff][x.ss] + 1;
			q.push(t);
		}
	}
}

bool BFS2(queue<pairs> q, vec<vec<char>>& p, vec<vec<int>>& d, int& s, pairs& e, int& c) {
	vec<vec<int>> d2(p.size(), vec<int>(p.size(), -1));
	d2[q.front().ff][q.front().ss] = 0;
	if (d2[q.front().ff][q.front().ss] >= (d[q.front().ff][q.front().ss] - c)) return false;
	while (!q.empty()) {
		pairs x = q.front(); q.pop();
		if (x.ff == e.ff && x.ss == e.ss) return true;
		For(i, 4) {
			pairs t = { x.ff + r[i].ff, x.ss + r[i].ss };
			if (t.ff < 0 || t.ss < 0 || t.ff >= p.size() || t.ss >= p.size()) {
				continue;
			}
			if (p[t.ff][t.ss] == 'T' || d2[t.ff][t.ss] != -1) continue;
			d2[t.ff][t.ss] = d2[x.ff][x.ss] + 1;
			if ((d2[t.ff][t.ss] / s) >= (d[t.ff][t.ss] - c) && d[t.ff][t.ss] != -1) continue;
			q.push(t);
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin("atlarge.in");
	//ofstream cout("atlarge.out");
	int n, v;
	cin >> n >> v;
	vec<vec<char>> p(n, vec<char>(n));
	pairs s, e;
	queue<pairs> q;
	vec<vec<int>> d1(n, vec<int>(n, -1));
	For(i, n) {
		For(j, n) {
			cin >> p[i][j];
			if (p[i][j] == 'M') {
				s = { i, j };
			}
			if (p[i][j] == 'D') {
				e = { i, j };
			}
			if (p[i][j] == 'H') {
				q.push({ i, j });
				d1[i][j] = 0;
			}
		}
	}
	BFS(q, p, d1);
	int l = 0, r = n*n;
	q.push(s);
	while (l < r) {
		int c = (l + r) / 2 + 1;
		if (BFS2(q, p, d1, v, e, c)) l = c;
		else r = c-1;
	}
	if (BFS2(q, p, d1, v, e, l)) cout << l << '\n';
	else cout << -1 << '\n';
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void BFS(std::queue<std::pair<int, int> >&, std::vector<std::vector<char> >&, std::vector<std::vector<int> >&)':
mecho.cpp:25:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |    if (t.ff < 0 || t.ss < 0 || t.ff >= p.size() || t.ss >= p.size()) continue;
      |                                ~~~~~^~~~~~~~~~~
mecho.cpp:25:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |    if (t.ff < 0 || t.ss < 0 || t.ff >= p.size() || t.ss >= p.size()) continue;
      |                                                    ~~~~~^~~~~~~~~~~
mecho.cpp: In function 'bool BFS2(std::queue<std::pair<int, int> >, std::vector<std::vector<char> >&, std::vector<std::vector<int> >&, int&, std::pair<int, int>&, int&)':
mecho.cpp:43:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (t.ff < 0 || t.ss < 0 || t.ff >= p.size() || t.ss >= p.size()) {
      |                                ~~~~~^~~~~~~~~~~
mecho.cpp:43:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (t.ff < 0 || t.ss < 0 || t.ff >= p.size() || t.ss >= p.size()) {
      |                                                    ~~~~~^~~~~~~~~~~

• Subtask 1: 100 / 100