Submission #1098820

# Submission time Handle Problem Language Result Execution time Memory
1098820 2024-10-10T05:51:54 Z damamila Mecho (IOI09_mecho) C++14
8 / 100
1000 ms 65536 KB
#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;
}

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 (check(x3+x, y3+y)) ans = max(ans, dist[x3+x][y3+y]);
	}
	cout << ans << endl;
}

Compilation message

mecho.cpp: In function 'void bfs1()':
mecho.cpp:35:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |   auto [d, i, j] = q.front();
      |        ^
mecho.cpp:39:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |   for (auto [x, y] : direc) {
      |             ^
mecho.cpp: In function 'void bfs2()':
mecho.cpp:49:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |   auto [d, i, j, step] = pq.top();
      |        ^
mecho.cpp:63:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |   for (auto [x, y] : direc) {
      |             ^
mecho.cpp: In function 'int main()':
mecho.cpp:105:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |  for (auto [x, y] : direc) {
      |            ^
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Runtime error 145 ms 65536 KB Execution killed with signal 9
8 Incorrect 1 ms 600 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Runtime error 409 ms 65536 KB Execution killed with signal 9
14 Runtime error 595 ms 65536 KB Execution killed with signal 9
15 Incorrect 1 ms 348 KB Output isn't correct
16 Correct 26 ms 860 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Correct 174 ms 1432 KB Output is correct
19 Incorrect 1 ms 344 KB Output isn't correct
20 Runtime error 334 ms 65536 KB Execution killed with signal 9
21 Incorrect 0 ms 348 KB Output isn't correct
22 Execution timed out 1012 ms 65536 KB Time limit exceeded
23 Incorrect 1 ms 348 KB Output isn't correct
24 Execution timed out 1094 ms 16968 KB Time limit exceeded
25 Incorrect 1 ms 344 KB Output isn't correct
26 Runtime error 690 ms 65536 KB Execution killed with signal 9
27 Incorrect 1 ms 344 KB Output isn't correct
28 Runtime error 389 ms 65536 KB Execution killed with signal 9
29 Incorrect 1 ms 344 KB Output isn't correct
30 Runtime error 350 ms 65536 KB Execution killed with signal 9
31 Incorrect 1 ms 600 KB Output isn't correct
32 Runtime error 508 ms 65536 KB Execution killed with signal 9
33 Incorrect 5 ms 3420 KB Output isn't correct
34 Runtime error 194 ms 65536 KB Execution killed with signal 9
35 Correct 20 ms 3676 KB Output is correct
36 Incorrect 7 ms 4444 KB Output isn't correct
37 Runtime error 209 ms 65536 KB Execution killed with signal 9
38 Correct 26 ms 4440 KB Output is correct
39 Incorrect 9 ms 5468 KB Output isn't correct
40 Runtime error 211 ms 65536 KB Execution killed with signal 9
41 Correct 35 ms 5692 KB Output is correct
42 Incorrect 11 ms 6744 KB Output isn't correct
43 Runtime error 218 ms 65536 KB Execution killed with signal 9
44 Correct 44 ms 6748 KB Output is correct
45 Incorrect 14 ms 8028 KB Output isn't correct
46 Runtime error 203 ms 65536 KB Execution killed with signal 9
47 Correct 52 ms 8280 KB Output is correct
48 Incorrect 16 ms 9564 KB Output isn't correct
49 Runtime error 208 ms 65536 KB Execution killed with signal 9
50 Correct 62 ms 9560 KB Output is correct
51 Incorrect 18 ms 11100 KB Output isn't correct
52 Runtime error 217 ms 65536 KB Execution killed with signal 9
53 Correct 75 ms 11356 KB Output is correct
54 Incorrect 20 ms 12892 KB Output isn't correct
55 Runtime error 200 ms 65536 KB Execution killed with signal 9
56 Correct 86 ms 13140 KB Output is correct
57 Incorrect 23 ms 14684 KB Output isn't correct
58 Runtime error 205 ms 65536 KB Execution killed with signal 9
59 Correct 95 ms 14936 KB Output is correct
60 Incorrect 28 ms 16728 KB Output isn't correct
61 Runtime error 217 ms 65536 KB Execution killed with signal 9
62 Correct 121 ms 16980 KB Output is correct
63 Correct 132 ms 16872 KB Output is correct
64 Runtime error 319 ms 65536 KB Execution killed with signal 9
65 Execution timed out 1016 ms 49820 KB Time limit exceeded
66 Runtime error 718 ms 65536 KB Execution killed with signal 9
67 Incorrect 110 ms 16728 KB Output isn't correct
68 Runtime error 271 ms 65536 KB Execution killed with signal 9
69 Runtime error 224 ms 65536 KB Execution killed with signal 9
70 Runtime error 828 ms 65536 KB Execution killed with signal 9
71 Execution timed out 1074 ms 49660 KB Time limit exceeded
72 Runtime error 235 ms 65536 KB Execution killed with signal 9
73 Execution timed out 1050 ms 52492 KB Time limit exceeded
74 Runtime error 408 ms 65536 KB Execution killed with signal 9
75 Execution timed out 1097 ms 52764 KB Time limit exceeded
76 Execution timed out 1036 ms 52476 KB Time limit exceeded
77 Runtime error 347 ms 65536 KB Execution killed with signal 9
78 Runtime error 399 ms 65536 KB Execution killed with signal 9
79 Runtime error 235 ms 65536 KB Execution killed with signal 9
80 Execution timed out 1065 ms 52392 KB Time limit exceeded
81 Execution timed out 1072 ms 52416 KB Time limit exceeded
82 Execution timed out 1065 ms 35852 KB Time limit exceeded
83 Runtime error 395 ms 65536 KB Execution killed with signal 9
84 Runtime error 341 ms 65536 KB Execution killed with signal 9
85 Runtime error 182 ms 65536 KB Execution killed with signal 9
86 Runtime error 265 ms 65536 KB Execution killed with signal 9
87 Runtime error 137 ms 65536 KB Execution killed with signal 9
88 Runtime error 203 ms 65536 KB Execution killed with signal 9
89 Runtime error 483 ms 65536 KB Execution killed with signal 9
90 Runtime error 149 ms 65536 KB Execution killed with signal 9
91 Execution timed out 1040 ms 51448 KB Time limit exceeded
92 Runtime error 157 ms 65536 KB Execution killed with signal 9