# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
511162 | 600Mihnea | Mecho (IOI09_mecho) | C++17 | 157 ms | 16660 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 7;
const int INF = (int) 1e9 + 7;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int n;
int speed;
int r1, c1;
int r2, c2;
int a[N][N];
int dist_m[N][N];
int dist_b[N][N];
vector<pair<int, int>> ord;
void compute(int dist[N][N], vector<pair<int, int>> init) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = INF;
}
}
queue<pair<int, int>> q;
for (auto &it : init) {
dist[it.first][it.second] = 0;
q.push(it);
}
while (!q.empty()) {
auto it = q.front();
int r = it.first;
int c = it.second;
ord.push_back(it);
q.pop();
for (int k = 0; k < 4; k++) {
int rn = r + dr[k];
int cn = c + dc[k];
if (a[rn][cn] && dist[rn][cn] == INF) {
dist[rn][cn] = 1 + dist[r][c];
q.push({rn, cn});
}
}
}
}
int dist[N][N];
bool ok[N][N];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
/// freopen ("input", "r", stdin);
cin >> n >> speed;
vector<pair<int, int>> bees;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 1; j <= n; j++) {
char ch = s[j - 1];
if (ch == 'T') {
a[i][j] = 0;
continue;
}
if (ch == 'G') {
a[i][j] = 1;
continue;
}
if (ch == 'M') {
r1 = i;
c1 = j;
a[i][j] = 1;
continue;
}
if (ch == 'D') {
r2 = i;
c2 = j;
a[i][j] = 1;
continue;
}
if (ch == 'H') {
bees.push_back({i, j});
continue;
}
}
}
vector<pair<int, int>> m;
m.push_back({r1, c1});
compute(dist_b, bees);
ord.clear();
compute(dist_m, m);
int low = 0, high = dist_b[r1][c1], sol = -1;
while (low <= high) {
int stay = (low + high) / 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ok[i][j] = 0;
}
}
ok[r1][c1] = 1;
for (auto &it : ord) {
if (ok[it.first][it.second]) {
int r = it.first, c = it.second;
for (int k = 0; k < 4; k++) {
int rn = r + dr[k];
int cn = c + dc[k];
ok[rn][cn] |= (stay + (dist_m[rn][cn] + speed - 1) / speed <= dist_b[rn][cn]);
}
}
}
if (ok[r2][c2]) {
sol = stay;
low = stay + 1;
} else {
high = stay - 1;
}
}
cout << sol << "\n";
return 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int val = dist_m[i][j];
if (val == INF) {
cout << "- ";
} else {
cout << val << " ";
}
}
cout << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |