# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
413534 | LouayFarah | Wombats (IOI13_wombats) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#include "wombats.h"
using namespace std;
#define pb push_back
#define make_pair mp
#define fi first
#difine se second
int r, c;
vector<vector<int>> h, v;
void init(int R, int C, int H[][100], int V[][100])
{
r = R;
c = C;
h.resize(R);
for(int i = 0; i<R; i++)
h[i].resize(C-1);
v.resize(R-1);
for(int i = 0; i<R-1; i++)
v[i].resize(C);
for(int i = 0; i<r; i++)
{
for(int j = 0; j<c-1; j++)
{
h[i][j] = H[i][j];
}
}
for(int i = 0; i<r-1; i++)
{
for(int j = 0; j<c; j++)
{
v[i][j] = V[i][j];
}
}
}
void changeH(int P, int Q, int W)
{
h[P][Q] = W;
}
void changeV(int P, int Q, int W)
{
v[P][Q] = W;
}
int escape(int V1, int V2)
{
V2+=(r-1)*c;
vector<bool> visited(r*c, false);
vector<int> dist(r*c, 1e8);
priority_queue<pair<int, int>> pq;
pq.push(mp(0, V1));
dist[V1] = false;
while(!pq.empty())
{
int u = pq.top().se;
pq.pop();
if(visited[u])
continue;
visited[u] = true;
if((u%c)>0)
{
int b = u-1;
int w = h[b/c][b%c];
if(dist[u]+w<dist[b])
{
dist[b] = dist[u]+w;
pq.push(mp(-dist[b], b));
}
}
if((u%c)<c-1)
{
int b = u+1;
int w = h[u/c][u%c];
if(dist[u]+w<dist[b])
{
dist[b] = dist[u]+w;
pq.push(mp(-dist[b], b));
}
}
if((u-(r-1)*c)<0)
{
int b = u+c;
int w = v[u/c][u%c];
if(dist[u]+w<dist[b])
{
dist[b] = dist[u]+w;
pq.push(mp(-dist[b], b));
}
}
}
return dist[V2];
}