oj.uz

Submission #838432

# Submission time Handle Problem Language Result Execution time Memory
838432 2023-08-26T21:48:23 Z cryan Mecho (IOI09_mecho) C++17
9 / 100
 928 ms 65536 KB 
// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define f first
#define s second
#define pi pair<int, int>
#define endl '\n'
#ifdef LOCAL
#include "/mnt/c/yukon/pp.hpp"
#endif

vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, S;
	cin >> n >> S;

	vector<vector<int>> grid(n, vector<int>(n));
	pi st, ed;
	queue<array<int, 3>> q;
	vector<vector<int>> bist(n, vector<int>(n, 9));
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			if (s[j] == 'T') {
				grid[i][j] = -1;
			} else if (s[j] == 'G') {
				grid[i][j] = 0;
			} else if (s[j] == 'M') {
				grid[i][j] = 0;
				st = {i, j};
			} else if (s[j] == 'D') {
				grid[i][j] = 0;
				ed = {i, j};
			} else {
				grid[i][j] = 1;
				bist[i][j] = 0;
				q.push({i, j, 0});
			}
		}
	}

	// dist from hives first
	while (sz(q)) {
		auto [i, j, di] = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = i + dx[d], nj = j + dy[d];
			if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] != -1 && di + 1 < bist[ni][nj]) {
				bist[ni][nj] = di + 1;
				q.push({ni, nj, di + 1});
			}
		}
	}
	// for (int i = 0; i < n; i++) {
	// 	cerr << bist[i] << endl;
	// }

	vector<vector<pi>> fastest(n, vector<pi>(n, {-inf, 0}));
	fastest[st.f][st.s] = {bist[st.f][st.s], 1};

	q.push({st.f, st.s, 0});

	map<pi, pi> prev;
	while (sz(q)) {
		auto [i, j, d] = q.front();
		q.pop();
		// cout << "start from: " << i << ' ' << j << " with distance " << d << endl;

		for (int dir = 0; dir < 4; dir++) {
			int ni = i + dx[dir], nj = j + dy[dir];

			int mins = (d + 1) / S;

			if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] != -1) {
				if (mins <= bist[ni][nj]) {

					int best = min(fastest[i][j].f, bist[ni][nj] - mins);
					if (best == -inf) {
						// cout << "fastest[" << ni << "][" << nj << "] = {" << best << ", " << (bool)((d + 1) % S > 0) << "}" << endl;
						fastest[ni][nj] = {bist[ni][nj] - mins, (d + 1) % S > 0};
						prev[{ni, nj}] = {i, j};
						q.push({ni, nj, d + 1});
					} else if (best > fastest[ni][nj].f || (best == fastest[ni][nj].f && (d + 1) % S > fastest[ni][nj].s)) {
						// cout << "fastest[" << ni << "][" << nj << "] = {" << best << ", " << (bool)((d + 1) % S > 0) << "}" << endl;
						fastest[ni][nj] = {best, (d + 1) % S > 0};
						prev[{ni, nj}] = {i, j};
						q.push({ni, nj, d + 1});
					}
				}
			}
		}
	}
	// cout << "path:" << endl;
	// auto tmp = ed;
	// while (tmp != pi{0, 0}) {
	// 	cout << tmp << endl;
	// 	tmp = prev[tmp];
	// }

	cout << (fastest[ed.f][ed.s].f == -inf ? -1 : fastest[ed.f][ed.s].f - 1) << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

Subtask #1
9.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Runtime error 163 ms 65536 KB Execution killed with signal 9
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 2 ms 468 KB Output isn't correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 4 ms 596 KB Output isn't correct
19 Incorrect 0 ms 340 KB Output isn't correct
20 Incorrect 19 ms 2004 KB Output isn't correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Runtime error 233 ms 65536 KB Execution killed with signal 9
23 Incorrect 1 ms 340 KB Output isn't correct
24 Runtime error 248 ms 65536 KB Execution killed with signal 9
25 Incorrect 1 ms 340 KB Output isn't correct
26 Runtime error 229 ms 65536 KB Execution killed with signal 9
27 Incorrect 1 ms 340 KB Output isn't correct
28 Runtime error 234 ms 65536 KB Execution killed with signal 9
29 Incorrect 1 ms 340 KB Output isn't correct
30 Runtime error 235 ms 65536 KB Execution killed with signal 9
31 Incorrect 1 ms 340 KB Output isn't correct
32 Runtime error 258 ms 65536 KB Execution killed with signal 9
33 Incorrect 2 ms 2388 KB Output isn't correct
34 Runtime error 234 ms 65536 KB Execution killed with signal 9
35 Runtime error 240 ms 65536 KB Execution killed with signal 9
36 Incorrect 2 ms 3028 KB Output isn't correct
37 Runtime error 230 ms 65536 KB Execution killed with signal 9
38 Runtime error 235 ms 65536 KB Execution killed with signal 9
39 Incorrect 3 ms 3668 KB Output isn't correct
40 Runtime error 241 ms 65536 KB Execution killed with signal 9
41 Runtime error 244 ms 65536 KB Execution killed with signal 9
42 Incorrect 3 ms 4564 KB Output isn't correct
43 Runtime error 221 ms 65536 KB Execution killed with signal 9
44 Runtime error 233 ms 65536 KB Execution killed with signal 9
45 Incorrect 3 ms 5332 KB Output isn't correct
46 Runtime error 243 ms 65536 KB Execution killed with signal 9
47 Runtime error 227 ms 65536 KB Execution killed with signal 9
48 Incorrect 4 ms 6360 KB Output isn't correct
49 Runtime error 218 ms 65536 KB Execution killed with signal 9
50 Runtime error 222 ms 65536 KB Execution killed with signal 9
51 Incorrect 4 ms 7380 KB Output isn't correct
52 Runtime error 233 ms 65536 KB Execution killed with signal 9
53 Runtime error 226 ms 65536 KB Execution killed with signal 9
54 Incorrect 5 ms 8552 KB Output isn't correct
55 Runtime error 206 ms 65536 KB Execution killed with signal 9
56 Runtime error 224 ms 65536 KB Execution killed with signal 9
57 Incorrect 6 ms 9804 KB Output isn't correct
58 Runtime error 219 ms 65536 KB Execution killed with signal 9
59 Runtime error 213 ms 65536 KB Execution killed with signal 9
60 Incorrect 8 ms 11092 KB Output isn't correct
61 Runtime error 204 ms 65536 KB Execution killed with signal 9
62 Runtime error 232 ms 65536 KB Execution killed with signal 9
63 Incorrect 11 ms 11028 KB Output isn't correct
64 Runtime error 204 ms 65536 KB Execution killed with signal 9
65 Incorrect 9 ms 10964 KB Output isn't correct
66 Incorrect 8 ms 11092 KB Output isn't correct
67 Correct 8 ms 10964 KB Output is correct
68 Runtime error 203 ms 65536 KB Execution killed with signal 9
69 Runtime error 216 ms 65536 KB Execution killed with signal 9
70 Runtime error 555 ms 65536 KB Execution killed with signal 9
71 Incorrect 32 ms 11952 KB Output isn't correct
72 Runtime error 204 ms 65536 KB Execution killed with signal 9
73 Incorrect 365 ms 23400 KB Output isn't correct
74 Runtime error 172 ms 65536 KB Execution killed with signal 9
75 Incorrect 928 ms 45108 KB Output isn't correct
76 Incorrect 26 ms 11772 KB Output isn't correct
77 Runtime error 175 ms 65536 KB Execution killed with signal 9
78 Runtime error 209 ms 65536 KB Execution killed with signal 9
79 Runtime error 170 ms 65536 KB Execution killed with signal 9
80 Runtime error 212 ms 65536 KB Execution killed with signal 9
81 Incorrect 236 ms 20232 KB Output isn't correct
82 Runtime error 167 ms 65536 KB Execution killed with signal 9
83 Runtime error 199 ms 65536 KB Execution killed with signal 9
84 Runtime error 162 ms 65536 KB Execution killed with signal 9
85 Runtime error 166 ms 65536 KB Execution killed with signal 9
86 Runtime error 162 ms 65536 KB Execution killed with signal 9
87 Runtime error 165 ms 65536 KB Execution killed with signal 9
88 Runtime error 164 ms 65536 KB Execution killed with signal 9
89 Runtime error 167 ms 65536 KB Execution killed with signal 9
90 Runtime error 162 ms 65536 KB Execution killed with signal 9
91 Runtime error 166 ms 65536 KB Execution killed with signal 9
92 Runtime error 184 ms 65536 KB Execution killed with signal 9