| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 108573 | tictaccat | 로봇 (IOI13_robots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int sum, R, C;
vector<vector<int>> H(5050,vector<int>(210,INF)), V(5050,vector<int>(210,INF));
vector<vector<int>> ans(210,vector<int>(210,-1));
void init(int Rt, int Ct, int tH[5000][200], int tV[5000][200]) {
/* ... */
R = Rt; C = Ct;
for (int i = 0; i < 5000; i++) for (int j = 0; j < 200; j++) {H[i][j] = tH[i][j]; V[i][j] = tV[i][j];}
}
void changeH(int P, int Q, int W) {
/* ... */
H[P][Q] = W;
ans.clear();
}
void changeV(int P, int Q, int W) {
/* ... */
V[P][Q] = W;
ans.clear();
ans.assign(210,vector<int>(210,-1));
}
int escape(int V1, int V2) {
// assert(V1 == 0 && V2 == 0);
if (ans[V1][V2] != -1) {
//cout << "test\n";
return ans[V1][V2];
}
priority_queue<tuple<int,int,int>> pq;
vector<vector<int>> dist(R,vector<int>(C,-1));
pq.push(make_tuple(0,V1,0));
while (!pq.empty()) {
int c,r,d; tie(d,c,r) = pq.top(); pq.pop();
if (dist[r][c] != -1) continue;
d *= -1;
dist[r][c] = d;
if (c > 0 && (dist[r][c-1] == -1 || dist[r][c-1] > d + H[r][c-1])) pq.push(make_tuple(-(d + H[r][c-1]),c-1,r));
if (c < C-1 && (dist[r][c+1] == -1 || dist[r][c+1] > d + H[r][c])) pq.push(make_tuple(-(d + H[r][c]),c+1,r));
if (r < R-1 && (dist[r+1][c] == -1 || dist[r+1][c] > d + V[r][c])) pq.push(make_tuple(-(d + V[r][c]),c,r+1));
}
return (ans[V1][V2] = dist[R-1][V2]);
}