답안 #1098820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098820	2024-10-10T05:51:54 Z	damamila	Mecho (IOI09_mecho)	C++14	8 / 100	1000 ms	65536 KB

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<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) {
      |            ^

Subtask #1

8.0 / 100.0

#	결과	실행 시간	메모리	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