Submission #943476

#TimeUsernameProblemLanguageResultExecution timeMemory
943476myst6Mecho (IOI09_mecho)C++14
30 / 100
469 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 1 << 30; int di[4] = {1, -1, 0, 0}; int dj[4] = {0, 0, 1, -1}; int main() { cin.tie(0)->sync_with_stdio(0); int N, S; cin >> N >> S; vector<string> grid(N); for (int i=0; i<N; i++) { cin >> grid[i]; } vector<vector<int>> dist(N, vector<int>(N, inf)); queue<pair<int,int>> Q; for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (grid[i][j] == 'H') { dist[i][j] = 0; Q.push({i, j}); } } } while (Q.size()) { auto [i, j] = Q.front(); Q.pop(); for (int k=0; k<4; k++) { int i2 = i + di[k]; int j2 = j + dj[k]; if (i2 < 0 || j2 < 0 || i2 >= N || j2 >= N) continue; if (grid[i2][j2] != 'G') continue; if (dist[i2][j2] <= dist[i][j]) continue; dist[i2][j2] = dist[i][j] + 1; Q.push({i2, j2}); } } pair<int,int> begin, end; for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (grid[i][j] == 'M') { begin = {i, j}; } else if (grid[i][j] == 'D') { end = {i, j}; } } } int lo = 0, hi = 1 << 30, ans = 0; while (lo <= hi) { int mid = (lo + hi) / 2; // mid = number of steps the bees have progressed already vector<vector<int>> dist2(N, vector<int>(N, inf)); dist2[begin.first][begin.second] = 0; queue<pair<int,int>> Q; Q.push(begin); while (Q.size()) { auto [i, j] = Q.front(); Q.pop(); for (int k=0; k<4; k++) { int i2 = i + di[k]; int j2 = j + dj[k]; if (i2 < 0 || j2 < 0 || i2 >= N || j2 >= N) continue; if (grid[i2][j2] != 'G' && grid[i2][j2] != 'D') continue; if (dist2[i2][j2] <= dist2[i][j]) continue; int T = mid + (dist2[i][j] + 1) / S; if (dist[i2][j2] <= T) continue; dist2[i2][j2] = dist2[i][j] + 1; Q.push({i2, j2}); } } if (dist2[end.first][end.second] == inf) { hi = mid - 1; } else { ans = mid; lo = mid + 1; } } cout << ans << "\n"; return 0; }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:28:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     auto [i, j] = Q.front(); Q.pop();
      |          ^
mecho.cpp:58:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |       auto [i, j] = Q.front(); Q.pop();
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...