| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1022288 | amine_aroua | Wombats (IOI13_wombats) | C++17 | 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 "wombats.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> h , v;
int r , c;
int xx[3] = {1 , 0 , 0};
int yy[3] = {0 , -1 , 1};
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R;
c = C;
h.assign(R , vector<int>(C));
v = h;
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) {
priority_queue<pair<int ,pair<int ,int>> ,vector<pair<int ,pair<int,int>>>, greater<pair<int ,pair<int, int>>>> pq;
pq.push({0 , {0 , V1}});
vector<bitset<200>> vis(r);
vector<vector<int>> dist(r , vector<int>(c , 2e9));
dist[0][V1] = 0;
while(!pq.empty())
{
auto [d , p] = pq.top();
auto [i , j] = p;
pq.pop();
if(vis[i][j])
continue;
vis[i][j] = 1;
for(int k = 0 ; k < 3 ; k++)
{
int ni = i + xx[k] , nj = j + yy[k];
if(ni >= 0 && nj >= 0 && ni < r && nj < c)
{
int cost = 0;
if(xx[k] == 1)
cost = v[i][j];
if(yy[k] == 1)
cost = h[i][j];
if(yy[k] == -1)
cost = h[i][j - 1];
if(dist[ni][nj] > dist[i][j] + cost)
{
dist[ni][nj] = dist[i][j] + cost;
pq.push({dist[ni][nj] , {ni , nj}});
}
}
}
}
return dist[r - 1][V2];
}
int main()
{
int a , b;
cin>>a>>b;
int hh[5000][200] ,vv[5000][200];
for(int i = 0 ; i < a ; i++)
{
for(int j = 0 ; j + 1 < b ; j++)
{
cin>>hh[i][j];
}
}
for(int i = 0 ; i + 1 < a ; i++)
{
for(int j = 0 ; j < b ; j++)
{
cin>>vv[i][j];
}
}
init(a , b , hh , vv);
int e;
cin>>e;
while (e--)
{
int t;
cin>>t;
if(t == 1)
{
int p , q ,w;
cin>>p>>q>>w;
changeH(p , q , w);
}
else if(t == 2)
{
int p , q ,w;
cin>>p>>q>>w;
changeV(p , q , w);
}
else
{
int v1 ,v2;
cin>>v1>>v2;
cout<<escape(v1 ,v2)<<'\n';
}
}
}