oj.uz

답안 #1098821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1098821 2024-10-10T05:54:10 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;
}

bool check2(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' || grid[i][j] == 'D') 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 (check2(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:41:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   auto [d, i, j] = q.front();
      |        ^
mecho.cpp:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for (auto [x, y] : direc) {
      |             ^
mecho.cpp: In function 'void bfs2()':
mecho.cpp:55:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |   auto [d, i, j, step] = pq.top();
      |        ^
mecho.cpp:69:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |   for (auto [x, y] : direc) {
      |             ^
mecho.cpp: In function 'int main()':
mecho.cpp:111:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |  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 1 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Runtime error 144 ms 65536 KB Execution killed with signal 9
8 Incorrect 1 ms 604 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 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 415 ms 65536 KB Execution killed with signal 9
14 Runtime error 604 ms 65536 KB Execution killed with signal 9
15 Incorrect 0 ms 600 KB Output isn't correct
16 Correct 26 ms 860 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Correct 178 ms 1620 KB Output is correct
19 Incorrect 0 ms 344 KB Output isn't correct
20 Runtime error 303 ms 65536 KB Execution killed with signal 9
21 Incorrect 1 ms 344 KB Output isn't correct
22 Execution timed out 1034 ms 33428 KB Time limit exceeded
23 Incorrect 0 ms 348 KB Output isn't correct
24 Execution timed out 1093 ms 16848 KB Time limit exceeded
25 Incorrect 1 ms 344 KB Output isn't correct
26 Runtime error 682 ms 65536 KB Execution killed with signal 9
27 Incorrect 1 ms 348 KB Output isn't correct
28 Runtime error 375 ms 65536 KB Execution killed with signal 9
29 Incorrect 1 ms 348 KB Output isn't correct
30 Runtime error 340 ms 65536 KB Execution killed with signal 9
31 Incorrect 1 ms 600 KB Output isn't correct
32 Runtime error 495 ms 65536 KB Execution killed with signal 9
33 Incorrect 5 ms 3420 KB Output isn't correct
34 Runtime error 210 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 205 ms 65536 KB Execution killed with signal 9
38 Correct 26 ms 4444 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 34 ms 5724 KB Output is correct
42 Incorrect 10 ms 6748 KB Output isn't correct
43 Runtime error 202 ms 65536 KB Execution killed with signal 9
44 Correct 43 ms 6952 KB Output is correct
45 Incorrect 13 ms 8024 KB Output isn't correct
46 Runtime error 197 ms 65536 KB Execution killed with signal 9
47 Correct 57 ms 8284 KB Output is correct
48 Incorrect 16 ms 9476 KB Output isn't correct
49 Runtime error 206 ms 65536 KB Execution killed with signal 9
50 Correct 64 ms 9564 KB Output is correct
51 Incorrect 17 ms 11096 KB Output isn't correct
52 Runtime error 217 ms 65536 KB Execution killed with signal 9
53 Correct 73 ms 11388 KB Output is correct
54 Incorrect 20 ms 12888 KB Output isn't correct
55 Runtime error 208 ms 65536 KB Execution killed with signal 9
56 Correct 86 ms 13116 KB Output is correct
57 Incorrect 23 ms 14684 KB Output isn't correct
58 Runtime error 202 ms 65536 KB Execution killed with signal 9
59 Correct 111 ms 14940 KB Output is correct
60 Incorrect 26 ms 16728 KB Output isn't correct
61 Runtime error 208 ms 65536 KB Execution killed with signal 9
62 Correct 113 ms 16976 KB Output is correct
63 Correct 123 ms 16872 KB Output is correct
64 Runtime error 290 ms 65536 KB Execution killed with signal 9
65 Execution timed out 1028 ms 65536 KB Time limit exceeded
66 Runtime error 708 ms 65536 KB Execution killed with signal 9
67 Incorrect 117 ms 16728 KB Output isn't correct
68 Runtime error 274 ms 65536 KB Execution killed with signal 9
69 Runtime error 221 ms 65536 KB Execution killed with signal 9
70 Runtime error 836 ms 65536 KB Execution killed with signal 9
71 Execution timed out 1071 ms 49868 KB Time limit exceeded
72 Runtime error 244 ms 65536 KB Execution killed with signal 9
73 Execution timed out 1099 ms 52340 KB Time limit exceeded
74 Runtime error 409 ms 65536 KB Execution killed with signal 9
75 Execution timed out 1060 ms 52500 KB Time limit exceeded
76 Execution timed out 1076 ms 52456 KB Time limit exceeded
77 Runtime error 334 ms 65536 KB Execution killed with signal 9
78 Runtime error 417 ms 65536 KB Execution killed with signal 9
79 Runtime error 256 ms 65536 KB Execution killed with signal 9
80 Execution timed out 1026 ms 52384 KB Time limit exceeded
81 Execution timed out 1022 ms 52392 KB Time limit exceeded
82 Execution timed out 1016 ms 35816 KB Time limit exceeded
83 Runtime error 423 ms 65536 KB Execution killed with signal 9
84 Runtime error 343 ms 65536 KB Execution killed with signal 9
85 Runtime error 172 ms 65536 KB Execution killed with signal 9
86 Runtime error 270 ms 65536 KB Execution killed with signal 9
87 Runtime error 135 ms 65536 KB Execution killed with signal 9
88 Runtime error 178 ms 65536 KB Execution killed with signal 9
89 Runtime error 483 ms 65536 KB Execution killed with signal 9
90 Runtime error 150 ms 65536 KB Execution killed with signal 9
91 Execution timed out 1077 ms 51496 KB Time limit exceeded
92 Runtime error 166 ms 65536 KB Execution killed with signal 9