Submission #1098825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098825		damamila	Mecho (IOI09_mecho)	C++14	32 / 100	1095 ms	65536 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, s;
int x3, x2, y3, y2;
vector<vector<char>> grid;
vector<vector<int>> tim; //saves time the bees get there
vector<vector<int>> dist; //saves latest time can leave current spot to get to house on time
vector<vector<int>> steps;

vector<pair<int, int>> direc = {
	{1, 0},
	{-1, 0},
	{0, 1},
	{0, -1}
};

bool check(int i, int j) {
	if (i < 0 || j < 0 || i == n || j == n) return false; //out of bounds
	if (grid[i][j] == 'M' || grid[i][j] == 'G') return true; //good next field
	return false;
}

bool check2(int i, int j) {
	if (i < 0 || j < 0 || i == n || j == n) return false; //out of bounds
	if (grid[i][j] == 'M' || grid[i][j] == 'G' || grid[i][j] == 'D') return true; //good next field
	return false;
}

void bfs1() {
	queue<tuple<int, int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == 'H') q.push({0, i, j});
		}
	}
	while (!q.empty()) {
		auto [d, i, j] = q.front();
		q.pop();
		if (tim[i][j] <= d) continue;
		tim[i][j] = d;
		for (auto [x, y] : direc) {
			if (check(i+x, j+y)) q.push({d+1, i+x, j+y});
		}
	}
}

void bfs2() {
	priority_queue<tuple<int, int, int, int>> pq; //dist, i, j, steps left
	pq.push({1e9, x2, y2, s});
	while (!pq.empty()) {
		auto [d, i, j, step] = pq.top();
		//~ cout << d << " " << i << " " << j << " " << step << endl;
		pq.pop();
		if (tim[i][j] <= d) {
			d = tim[i][j]-1;
			step = s;
		}
		if (step == 0) {
			d--;
			step = s;
		}
		if (dist[i][j] > d || (dist[i][j] == d && steps[i][j] >= d)) continue;
		dist[i][j] = d;
		steps[i][j] = step;
		for (auto [x, y] : direc) {
			if (check(i+x, j+y)) pq.push({d, i+x, j+y, step-1});
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	cin >> n >> s;
	grid = vector<vector<char>> (n, vector<char> (n));
	tim = vector<vector<int>> (n, vector<int> (n, 1e9));
	dist = vector<vector<int>> (n, vector<int> (n, -1));
	steps = vector<vector<int>> (n, vector<int> (n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == 'D') {
				x2 = i; y2 = j;
			}
			if (grid[i][j] == 'M') {
				x3 = i; y3 = j;
			}
		}
	}
	bfs1(); //calculates how long it takes for fields to be infected with bees
	//~ for (int i = 0; i < n; i++) {
		//~ for (int j = 0; j < n; j++) {
			//~ cout << tim[i][j] << " ";
		//~ }
		//~ cout << endl;
	//~ }
	//now need to calc movement somehow
	bfs2();
	//~ for (int i = 0; i < n; i++) {
		//~ for (int j = 0; j < n; j++) {
			//~ cout << dist[i][j] << " ";
		//~ }
		//~ cout << endl;
	//~ }
	//~ int ans = 0;
	//~ for (auto [x, y] : direc) {
		//~ if (check2(x3+x, y3+y)) ans = max(ans, dist[x3+x][y3+y]);
	//~ }
	//~ cout << ans << endl;
	cout << dist[x3][y3] << endl;
}

Compilation message (stderr)

mecho.cpp: In function 'void bfs1()':
mecho.cpp:41:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   auto [d, i, j] = q.front();
      |        ^
mecho.cpp:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for (auto [x, y] : direc) {
      |             ^
mecho.cpp: In function 'void bfs2()':
mecho.cpp:55:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |   auto [d, i, j, step] = pq.top();
      |        ^
mecho.cpp:69:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |   for (auto [x, y] : direc) {
      |             ^

• Subtask 1: 32 / 100