oj.uz

답안 #843983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843983 2023-09-04T19:34:02 Z cryan Mecho (IOI09_mecho) C++17
4 / 100
 1000 ms 8780 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>
#ifdef LOCAL
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl '\n'
#endif

struct Event {
	pi loc;
	int dist;
};
const vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n;
	cin >> n;

	int S;
	cin >> S;

	vector<vector<int>> grid(n, vector<int>(n));
	vector<pi> hives;
	pi start, end;

	for (int i = 0; i < n; i++) {
		string st;
		cin >> st;

		for (int j = 0; j < n; j++) {
			if (st[j] == 'T')
				grid[i][j] = -1;
			else if (st[j] != 'D')
				grid[i][j] = 0;
			else
				grid[i][j] = 1, end = {i, j};

			if (st[j] == 'H') {
				hives.emplace_back(i, j);
			} else if (st[j] == 'M')
				start = {i, j};
		}
	}

	// let's get distance from bees first
	queue<Event> bfs;

	vector<vector<int>> dist_bees(n, vector<int>(n, inf));
	for (auto &[i, j] : hives) {
		bfs.push({{i, j}, 0});
		dist_bees[i][j] = 0;
	}
	while (!bfs.empty()) {
		auto [i, j] = bfs.front().loc;
		int dist = bfs.front().dist;
		bfs.pop();

		if (dist_bees[i][j] < dist)
			continue;

		for (int d = 0; d < 4; d++) {
			int new_i = i + dx[d], new_j = j + dy[d];

			if (new_i >= 0 && new_i < n && new_j >= 0 && new_j < n) {
				if (grid[new_i][new_j] != -1 && dist_bees[new_i][new_j] > dist + 1 && pi{new_i, new_j} != end) {
					dist_bees[new_i][new_j] = dist + 1;
					bfs.push({{new_i, new_j}, dist + 1});
				}
			}
		}
	}
	// for (int i = 0; i < n; i++) {
	// 	cout << dist_bees[i] << endl;
	// }

	// now mecho's turn
	bfs.push({{start.f, start.s}, 0});
	// just store distance w/o S factor
	vector<vector<int>> mecho_dist(n, vector<int>(n, -inf));
	mecho_dist[start.f][start.s] = dist_bees[start.f][start.s];

	while (sz(bfs)) {
		auto [i, j] = bfs.front().loc;
		int dist = bfs.front().dist;
		bfs.pop();
		// if (mecho_dist[i][j] < dist)
		// continue;
		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)
				continue;

			int elapsed = (dist + 1) / S;
			// if (ni == 3 && nj == 3) {
			// 	cout << dist + 1 << ' ' << elapsed << ' ' << dist_bees[ni][nj] << endl;
			// }
			int lead = min(mecho_dist[i][j], dist_bees[ni][nj] - elapsed);
			if (grid[ni][nj] != -1 && mecho_dist[ni][nj] < lead && elapsed < dist_bees[ni][nj]) {
				mecho_dist[ni][nj] = lead;
				bfs.push({{ni, nj}, dist + 1});
			}
		}
	}
	// cout << "________" << endl;
	// for (int i = 0; i < n; i++) {
	// 	cout << mecho_dist[i] << endl;
	// }
	// cout << "________" << endl;
	// for (int i = 0; i < n; i++) {
	// 	cout << mecho_lead[i] << endl;
	// }

	int ans = -inf;
	for (int d = 0; d < 4; d++) {
		int ni = end.f + dx[d], nj = end.s + dy[d];

		if (ni < 0 || ni >= n || nj < 0 || nj >= n)
			continue;
		if (grid[ni][nj] == -1 || mecho_dist[ni][nj] == inf)
			continue;

		ans = max(ans, (mecho_dist[ni][nj] + S) / S);
		// int elapsed = (mecho_dist[ni][nj] + S) / S;
		// ans = max(ans, dist_bees[ni][nj] - elapsed);
	}
	cout << ans << 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
4.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 39 ms 8024 KB Output isn't correct
8 Incorrect 0 ms 344 KB Output isn't correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Incorrect 0 ms 344 KB Output isn't correct
11 Incorrect 0 ms 344 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 1 ms 344 KB Output isn't correct
14 Incorrect 1 ms 344 KB Output isn't correct
15 Incorrect 0 ms 344 KB Output isn't correct
16 Incorrect 0 ms 344 KB Output isn't correct
17 Incorrect 0 ms 344 KB Output isn't correct
18 Incorrect 0 ms 344 KB Output isn't correct
19 Incorrect 0 ms 344 KB Output isn't correct
20 Incorrect 1 ms 344 KB Output isn't correct
21 Incorrect 1 ms 344 KB Output isn't correct
22 Incorrect 1 ms 344 KB Output isn't correct
23 Incorrect 0 ms 344 KB Output isn't correct
24 Incorrect 0 ms 344 KB Output isn't correct
25 Incorrect 1 ms 344 KB Output isn't correct
26 Incorrect 1 ms 344 KB Output isn't correct
27 Incorrect 1 ms 344 KB Output isn't correct
28 Incorrect 1 ms 344 KB Output isn't correct
29 Incorrect 1 ms 548 KB Output isn't correct
30 Incorrect 1 ms 348 KB Output isn't correct
31 Incorrect 0 ms 512 KB Output isn't correct
32 Incorrect 0 ms 344 KB Output isn't correct
33 Incorrect 4 ms 1880 KB Output isn't correct
34 Incorrect 4 ms 1884 KB Output isn't correct
35 Incorrect 130 ms 1880 KB Output isn't correct
36 Incorrect 4 ms 2392 KB Output isn't correct
37 Incorrect 5 ms 2136 KB Output isn't correct
38 Incorrect 200 ms 2712 KB Output isn't correct
39 Incorrect 5 ms 2648 KB Output isn't correct
40 Incorrect 8 ms 2652 KB Output isn't correct
41 Incorrect 276 ms 2904 KB Output isn't correct
42 Incorrect 6 ms 3416 KB Output isn't correct
43 Incorrect 7 ms 3420 KB Output isn't correct
44 Incorrect 385 ms 3712 KB Output isn't correct
45 Incorrect 8 ms 3928 KB Output isn't correct
46 Incorrect 9 ms 3928 KB Output isn't correct
47 Incorrect 500 ms 4432 KB Output isn't correct
48 Incorrect 9 ms 4696 KB Output isn't correct
49 Incorrect 10 ms 4696 KB Output isn't correct
50 Incorrect 704 ms 5140 KB Output isn't correct
51 Incorrect 11 ms 5464 KB Output isn't correct
52 Incorrect 12 ms 5468 KB Output isn't correct
53 Incorrect 853 ms 5712 KB Output isn't correct
54 Incorrect 12 ms 6232 KB Output isn't correct
55 Incorrect 14 ms 6232 KB Output isn't correct
56 Execution timed out 1027 ms 7164 KB Time limit exceeded
57 Incorrect 14 ms 7000 KB Output isn't correct
58 Incorrect 16 ms 7000 KB Output isn't correct
59 Execution timed out 1056 ms 7496 KB Time limit exceeded
60 Incorrect 16 ms 8024 KB Output isn't correct
61 Incorrect 19 ms 8024 KB Output isn't correct
62 Execution timed out 1058 ms 8780 KB Time limit exceeded
63 Incorrect 36 ms 8016 KB Output isn't correct
64 Incorrect 41 ms 8020 KB Output isn't correct
65 Incorrect 38 ms 8028 KB Output isn't correct
66 Incorrect 35 ms 8024 KB Output isn't correct
67 Incorrect 31 ms 8020 KB Output isn't correct
68 Incorrect 30 ms 8016 KB Output isn't correct
69 Incorrect 33 ms 8024 KB Output isn't correct
70 Incorrect 30 ms 8020 KB Output isn't correct
71 Incorrect 28 ms 8016 KB Output isn't correct
72 Incorrect 31 ms 8016 KB Output isn't correct
73 Correct 25 ms 8024 KB Output is correct
74 Incorrect 57 ms 8024 KB Output isn't correct
75 Incorrect 26 ms 8024 KB Output isn't correct
76 Incorrect 26 ms 8024 KB Output isn't correct
77 Incorrect 27 ms 8024 KB Output isn't correct
78 Incorrect 29 ms 8024 KB Output isn't correct
79 Incorrect 295 ms 8584 KB Output isn't correct
80 Incorrect 45 ms 8140 KB Output isn't correct
81 Incorrect 29 ms 8480 KB Output isn't correct
82 Incorrect 81 ms 8024 KB Output isn't correct
83 Incorrect 30 ms 8024 KB Output isn't correct
84 Incorrect 78 ms 8024 KB Output isn't correct
85 Incorrect 143 ms 8416 KB Output isn't correct
86 Incorrect 171 ms 8272 KB Output isn't correct
87 Incorrect 44 ms 8024 KB Output isn't correct
88 Incorrect 102 ms 8024 KB Output isn't correct
89 Incorrect 327 ms 8364 KB Output isn't correct
90 Incorrect 33 ms 8024 KB Output isn't correct
91 Incorrect 51 ms 8128 KB Output isn't correct
92 Incorrect 34 ms 8028 KB Output isn't correct