제출 #629690

#제출 시각아이디문제언어결과실행 시간메모리
62969054skyxenonMecho (IOI09_mecho)Cpython 3
컴파일 에러
0 ms0 KiB
// From https://usaco.guide/problems/ioi-2009mecho/solution #include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define MAX_N 800 vector<string> field(MAX_N); int n, s; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int mechox, mechoy, home_x, home_y; vector<vector<bool>> bees_visited(MAX_N, vector<bool>(MAX_N)); vector<vector<int>> bees_time(MAX_N, vector<int>(MAX_N)); bool valid_sq(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n && (field[x][y] == 'G' || field[x][y] == 'M'); } bool mecho_reached(int mecho_dis, int bees_dis){ return mecho_dis / s < bees_dis; } bool ok(int eating_time) { vector<vector<bool>> mecho_visited(n, vector<bool>(n)); vector<vector<int>> mecho_time(n, vector<int>(n)); // move Mecho queue<pii> q; q.push({mechox, mechoy}); mecho_visited[mechox][mechoy] = true; if (bees_time[mechox][mechoy] <= eating_time) { q.pop(); } while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; /* * check if mecho reaces node[x][y] before the bees * divide the time mecho takes to reach a node by s, since * mecho walks s steps at a time. * substract the eating time from the time taken for the * bees to reach the node, because that time was used by * mecho for eating */ if (valid_sq(nx, ny) && !mecho_visited[nx][ny] && mecho_reached(mecho_time[x][y] + 1, bees_time[nx][ny] - eating_time)) { mecho_visited[nx][ny] = true; q.push({nx, ny}); mecho_time[nx][ny] = mecho_time[x][y] + 1; } } } // check if mecho reached a node surrounding his cave before the bees for (int i = 0; i < 4; i++) { int nx = home_x + dx[i], ny = home_y + dy[i]; if (valid_sq(nx, ny) && mecho_reached(mecho_time[nx][ny], bees_time[nx][ny] - eating_time) && mecho_visited[nx][ny]) { return true; } } return false; } int bs(int lo, int hi) { if (lo > hi) { return -1; } int mid = (lo + hi) / 2; if (!ok(mid)) { return bs(lo, mid - 1); } else if (mid < hi && ok(mid + 1)) { return bs(mid + 1, hi); } else { return mid; } } int main() { cin >> n >> s; for (int i = 0; i < n; i++) { cin >> field[i]; } vector<pii> hives; // find x and y coordinates for for Mecho, the bees and the cave for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (field[i][j] == 'M') { mechox = i; mechoy = j; } else if (field[i][j] == 'H') { hives.push_back({i, j}); } else if (field[i][j] == 'D') { home_x = i; home_y = j; } } } // move bees queue<pii> q; for (auto i : hives) { q.push({i.first, i.second}); bees_visited[i.first][i.second] = true; } while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (valid_sq(nx, ny) && !bees_visited[nx][ny]) { bees_time[nx][ny] = bees_time[x][y] + 1; q.push({nx, ny}); bees_visited[nx][ny] = true; } } } // binary search on waiting time cout << bs(0, n * n) << "\n"; }

컴파일 시 표준 에러 (stderr) 메시지

File "mecho.py", line 1
    // From https://usaco.guide/problems/ioi-2009mecho/solution
    ^
SyntaxError: invalid syntax