답안 #843979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
843979	2023-09-04T19:16:09 Z	cryan	Mecho (IOI09_mecho)	C++17	26 / 100	42 ms	11604 KB

mecho

// 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));
	vector<vector<int>> mecho_lead(n, vector<int>(n, 0));
	mecho_dist[start.f][start.s] = 0;
	mecho_lead[start.f][start.s] = dist_bees[start.f][start.s] - 1;

	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 + S) / S;
			if (grid[ni][nj] != -1 && mecho_dist[ni][nj] > dist + 1 && elapsed < dist_bees[ni][nj]) {
				mecho_dist[ni][nj] = dist + 1;
				mecho_lead[ni][nj] = min(dist_bees[ni][nj] - elapsed, mecho_lead[i][j]);
				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_lead[ni][nj]);
		// 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

26.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	348 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	Incorrect	0 ms	348 KB	Output isn't correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	32 ms	11196 KB	Output isn't correct
8	Incorrect	0 ms	344 KB	Output isn't correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Incorrect	0 ms	348 KB	Output isn't correct
15	Incorrect	0 ms	348 KB	Output isn't correct
16	Correct	0 ms	348 KB	Output is correct
17	Incorrect	0 ms	348 KB	Output isn't correct
18	Correct	0 ms	348 KB	Output is correct
19	Incorrect	0 ms	452 KB	Output isn't correct
20	Correct	0 ms	348 KB	Output is correct
21	Incorrect	0 ms	452 KB	Output isn't correct
22	Correct	0 ms	348 KB	Output is correct
23	Incorrect	0 ms	348 KB	Output isn't correct
24	Correct	0 ms	348 KB	Output is correct
25	Incorrect	0 ms	528 KB	Output isn't correct
26	Correct	0 ms	348 KB	Output is correct
27	Incorrect	0 ms	348 KB	Output isn't correct
28	Correct	1 ms	348 KB	Output is correct
29	Incorrect	1 ms	348 KB	Output isn't correct
30	Correct	1 ms	348 KB	Output is correct
31	Incorrect	0 ms	348 KB	Output isn't correct
32	Correct	0 ms	348 KB	Output is correct
33	Incorrect	4 ms	2352 KB	Output isn't correct
34	Correct	4 ms	2336 KB	Output is correct
35	Incorrect	5 ms	2336 KB	Output isn't correct
36	Incorrect	4 ms	3160 KB	Output isn't correct
37	Correct	5 ms	3024 KB	Output is correct
38	Incorrect	7 ms	3164 KB	Output isn't correct
39	Incorrect	5 ms	3676 KB	Output isn't correct
40	Correct	6 ms	3676 KB	Output is correct
41	Incorrect	9 ms	3828 KB	Output isn't correct
42	Incorrect	6 ms	4512 KB	Output isn't correct
43	Correct	7 ms	4560 KB	Output is correct
44	Incorrect	10 ms	4716 KB	Output isn't correct
45	Incorrect	11 ms	5724 KB	Output isn't correct
46	Correct	9 ms	5468 KB	Output is correct
47	Incorrect	12 ms	5564 KB	Output isn't correct
48	Incorrect	9 ms	6488 KB	Output isn't correct
49	Correct	10 ms	6492 KB	Output is correct
50	Incorrect	15 ms	6344 KB	Output isn't correct
51	Incorrect	10 ms	7516 KB	Output isn't correct
52	Correct	11 ms	7592 KB	Output is correct
53	Incorrect	16 ms	7516 KB	Output isn't correct
54	Incorrect	11 ms	8540 KB	Output isn't correct
55	Correct	14 ms	8540 KB	Output is correct
56	Incorrect	26 ms	9044 KB	Output isn't correct
57	Incorrect	14 ms	9820 KB	Output isn't correct
58	Correct	15 ms	9820 KB	Output is correct
59	Incorrect	22 ms	9808 KB	Output isn't correct
60	Incorrect	16 ms	11260 KB	Output isn't correct
61	Correct	17 ms	11100 KB	Output is correct
62	Incorrect	32 ms	11192 KB	Output isn't correct
63	Incorrect	32 ms	11052 KB	Output isn't correct
64	Correct	42 ms	11240 KB	Output is correct
65	Correct	40 ms	11100 KB	Output is correct
66	Incorrect	39 ms	11248 KB	Output isn't correct
67	Incorrect	33 ms	11060 KB	Output isn't correct
68	Incorrect	30 ms	11088 KB	Output isn't correct
69	Correct	32 ms	11088 KB	Output is correct
70	Correct	30 ms	11260 KB	Output is correct
71	Correct	29 ms	11072 KB	Output is correct
72	Correct	31 ms	11088 KB	Output is correct
73	Correct	29 ms	11604 KB	Output is correct
74	Correct	39 ms	11100 KB	Output is correct
75	Correct	26 ms	11100 KB	Output is correct
76	Correct	25 ms	11308 KB	Output is correct
77	Correct	29 ms	11100 KB	Output is correct
78	Incorrect	26 ms	11168 KB	Output isn't correct
79	Incorrect	40 ms	11100 KB	Output isn't correct
80	Correct	28 ms	11172 KB	Output is correct
81	Correct	28 ms	11088 KB	Output is correct
82	Incorrect	29 ms	11172 KB	Output isn't correct
83	Incorrect	26 ms	11100 KB	Output isn't correct
84	Incorrect	38 ms	11100 KB	Output isn't correct
85	Incorrect	28 ms	11100 KB	Output isn't correct
86	Incorrect	30 ms	11344 KB	Output isn't correct
87	Incorrect	28 ms	11100 KB	Output isn't correct
88	Incorrect	32 ms	11272 KB	Output isn't correct
89	Incorrect	40 ms	11220 KB	Output isn't correct
90	Incorrect	28 ms	11092 KB	Output isn't correct
91	Incorrect	32 ms	11092 KB	Output isn't correct
92	Incorrect	28 ms	11028 KB	Output isn't correct