Submission #1099055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099055		damamila	Mecho (IOI09_mecho)	C++14	100 / 100	449 ms	18856 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<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;
}

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, steps, i, j
	pq.push({1e9, s, x2, y2});
	while (!pq.empty()) {
		auto [d, step, i, j] = 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) continue;
		dist[i][j] = d;
		for (auto [x, y] : direc) {
			if (check(i+x, j+y)) pq.push({d, step-1, i+x, j+y});
		}
	}
}

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));
	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
	//now need to calc movement somehow
	bfs2(); //seg fault occurs in here
	cout << dist[x3][y3] << endl;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100