#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
int r, c;
int h[5000][200], v[5000][200];
int prefSums[5000];
int dists[5000][200];
int bigDists[200][200];
bool visited[5000][200];
priority_queue<pair<int, pair<int, int> > > q;
vector<pair<pair<int, int> , int> > graph[5000][200];
void distsFromCol(int x) {
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
dists[i][j] = 1000000000;
visited[i][j] = false;
}
}
pair<int, int> startNode = {0, x};
q.push({0, startNode});
dists[startNode.first][startNode.second] = 0;
while (!q.empty())
{
//cout << "in BFS\n";
int dist = q.top().first;
int nodex = q.top().second.first;
int nodey = q.top().second.second;
//cout << "At node " << node << " at dist " << dist << "\n";
q.pop();
if (!visited[nodex][nodey])
{
visited[nodex][nodey] = true;
dists[nodex][nodey] = min(-dist, dists[nodex][nodey]);
for (auto i : graph[nodex][nodey])
{
if (!visited[i.first.first][i.first.second])
{
q.push({dist-i.second, {i.first.first, i.first.second}});
//cout << "Pushing " << i.first << " at dist " << dist-i.second << "\n";
}
}
}
}
for (int i = 0; i < c; i++)
{
bigDists[x][i] = dists[r-1][i];
}
}
void changeH(int p, int q, int w) {
for (int i = 0; i < graph[p][q].size(); i++)
{
if (graph[p][q][i].first.first == p and graph[p][q][i].first.second == q+1)
{
//cout << "Change H part 1:" << graph[c*p+q][i].second << "\n";
graph[p][q][i].second = w;
//cout << "Changed to " << graph[c*p+q][i].second << "\n";
}
}
for (int i = 0; i < graph[p][q+1].size(); i++)
{
if (graph[p][q+1][i].first.first == p and graph[p][q+1][i].first.second == q)
{
//cout << "Change H part 2:" << graph[c*p+q+1][i].second << "\n";
graph[p][q+1][i].second = w;
//cout << "Changed to " << graph[c*p+q+1][i].second << "\n";
}
}
for (int i = 0; i < c; i++)
{
distsFromCol(i);
}
}
void changeV(int p, int q, int w){
if (c == 1)
{
int diff = w - (prefSums[p+1] - prefSums[p]);
for (int i = p+1; i < r; i++)
{
prefSums[i] += diff;
}
return;
}
for (int i = 0; i < graph[p][q].size(); i++)
{
if (graph[p][q][i].first.first == p+1 and graph[p][q][i].first.second == q)
{
//cout << "Change V: " << graph[c*p+q][i].second << "\n";
graph[p][q][i].second = w;
//cout << "Changed to " << graph[c*p+q][i].second << "\n";
}
}
for (int i = 0; i < c; i++)
{
distsFromCol(i);
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R;
c = C;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c-1; j++)
{
graph[i][j].push_back({{i,j+1}, H[i][j]});
graph[i][j+1].push_back({{i,j}, H[i][j]});
//cout << "Constructing graph\n";
}
}
for (int i = 0; i < r-1; i++)
{
for (int j = 0; j < c; j++)
{
graph[i][j].push_back({{i+1,j},V[i][j]});
//cout << "Constructing graph\n";
}
}
if (c == 1)
{
for (int i = 1; i < r; i++)
{
prefSums[i] = prefSums[i-1] + V[i-1][0];
}
}
}
int escape(int v1, int v2) {
if (c == 1)
{
return prefSums[r-1];
}
pair<int, int> startNode = {0, v1};
pair<int, int> endNode = {(r-1),v2};
//cout << "Going from " << startNode << " to " << endNode << "\n";
return bigDists[v1][v2];
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[p][q].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~
wombats.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[p][q+1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:93:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graph[p][q].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:145:20: warning: variable 'startNode' set but not used [-Wunused-but-set-variable]
pair<int, int> startNode = {0, v1};
^~~~~~~~~
wombats.cpp:146:20: warning: variable 'endNode' set but not used [-Wunused-but-set-variable]
pair<int, int> endNode = {(r-1),v2};
^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
27904 KB |
Output is correct |
| 2 |
Correct |
19 ms |
28024 KB |
Output is correct |
| 3 |
Correct |
102 ms |
29688 KB |
Output is correct |
| 4 |
Correct |
22 ms |
27904 KB |
Output is correct |
| 5 |
Correct |
19 ms |
27904 KB |
Output is correct |
| 6 |
Correct |
15 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 8 |
Correct |
17 ms |
23808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
23936 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20041 ms |
24932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
849 ms |
36984 KB |
Output is correct |
| 2 |
Correct |
1309 ms |
36984 KB |
Output is correct |
| 3 |
Correct |
858 ms |
36984 KB |
Output is correct |
| 4 |
Correct |
993 ms |
38300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20014 ms |
24932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20029 ms |
24832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
