| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 598980 | pakhomovee | 웜뱃 (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wombats.h"
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
int n, m;
int h[5000][200];
int v[5000][200];
int calc[200][200];
int dist[5000 * 200];
bool used[5000 * 200];
const int inf = 2e9;
void djkstra(int s, int* arr) {
priority_queue<pair<int, int>> q;
fill(dist, dist + n * m, inf);
fill(used, used + n * m, false);
dist[s] = 0;
q.push({ -dist[s], s });
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (used[u]) continue;
used[u] = true;
int r = u / m;
int c = u % m;
if (r + 1 < n && dist[u + m] > dist[u] + v[r][c]) {
dist[u + m] = dist[u] + v[r][c];
q.push({ -dist[u + m], u + m });
}
if (c > 0 && dist[u - 1] > dist[u] + h[r][c - 1]) {
dist[u - 1] = dist[u] + h[r][c - 1];
q.push({ -dist[u - 1], u - 1 });
}
if (c + 1 < m && dist[u + 1] > dist[u] + h[r][c]) {
dist[u + 1] = dist[u] + h[r][c];
q.push({ -dist[u], u });
}
}
for (int i = (n - 1) * m; i < n * m; ++i) {
arr[i - (n - 1) * m] = dist[i];
}
}
void recalc() {
for (int i = 0; i < m; ++i) {
djkstra(i, calc[i]);
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R;
m = C;
for (int i = 0; i < 5000; ++i) {
memcpy(h, H, 200 * sizeof(int));
}
for (int i = 0; i < 5000; ++i) {
memcpy(v, V, 200 * sizeof(int));
}
recalc();
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
recalc();
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
recalc();
}
int escape(int V1, int V2) {
assert(V1 < m);
assert(V2 < m);
return calc[V1][V2];
}