#include "wombats.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef pair<int, int> pi;
typedef pair<int, pi> p2i;
typedef priority_queue<p2i> djpq; // priority queue for djikstras
typedef vector<bool> vb;
typedef vector<vb> v2b;
#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
//sub1
v2i h, v;
int r, c;
int totw = 0;
bool sub1 = true;
bool sub2 = true;
bool sub3 = false;
bool sub4 = true;
v2i mindists;
v2b processed;
djpq q;
v3i s3dp; //sub 3 dp
void s3update(int r) {
int s, c;
if (r != 0) {
rep(s, 2) {
rep(c, 2) {
s3dp[r][c][s] = min(s3dp[r - 1][c][s] + v[r - 1][c], s3dp[r - 1][1 - c][s] + v[r - 1][1 - c] + h[r][0]);
}
}
}
else {
rep(s, 2) {
s3dp[0][1-s][s] = h[0][0];
}
}
}
void sub2calc(int start) {
//cout << "----------------------------Calculating minimum distances for " << start << "----------------------------\n";
q.push({ 0, {0, start} });
int d;
while (!q.empty()) {
p2i node = q.top();
d = 0 - node.first;
//cout << "Processing node (" << node.second.first << ", " << node.second.second << ") with distance " << d << "\n";
q.pop();
if (!processed[node.second.first][node.second.second]) {
//cout << "Adding children\n";
// process children of node
if (node.second.second < c - 1) { // right
//cout << "Added right node ";
int newdist = (d + h[node.second.first][node.second.second]);
q.push({ 0 - newdist, {node.second.first, node.second.second + 1} });
//cout << "with distance " << newdist << "\n";
}
if (node.second.second > 0) { // left
//cout << "Added left node ";
int newdist = (d + h[node.second.first][node.second.second - 1]);
q.push({ 0 - newdist, {node.second.first, node.second.second - 1} });
//cout << "with distance " << newdist << "\n";
}
if (node.second.first < r - 1) { // bottom
//cout << "Added bottom node ";
int newdist = (d + v[node.second.first][node.second.second]);
q.push({ 0 - newdist, {node.second.first + 1, node.second.second} });
//cout << "with distance " << newdist << "\n";
}
else {
mindists[start][node.second.second] = d;
//cout << "Minimum distance for " << node.second.second << " is " << d << "\n";
}
processed[node.second.first][node.second.second] = true;
}
}
}
int mindist4(int start, int end) {
//cout << "----------------------------Calculating minimum distances for " << start << "----------------------------\n";
q.push({ 0, {0, start} });
int d;
while (!q.empty()) {
p2i node = q.top();
d = 0 - node.first;
//cout << "Processing node (" << node.second.first << ", " << node.second.second << ") with distance " << d << "\n";
q.pop();
if (!processed[node.second.first][node.second.second]) {
//cout << "Adding children\n";
// process children of node
if (node.second.second < c - 1) { // right
//cout << "Added right node ";
int newdist = (d + h[node.second.first][node.second.second]);
q.push({ 0 - newdist, {node.second.first, node.second.second + 1} });
//cout << "with distance " << newdist << "\n";
}
if (node.second.second > 0) { // left
//cout << "Added left node ";
int newdist = (d + h[node.second.first][node.second.second - 1]);
q.push({ 0 - newdist, {node.second.first, node.second.second - 1} });
//cout << "with distance " << newdist << "\n";
}
if (node.second.first < r - 1) { // bottom
//cout << "Added bottom node ";
int newdist = (d + v[node.second.first][node.second.second]);
q.push({ 0 - newdist, {node.second.first + 1, node.second.second} });
//cout << "with distance " << newdist << "\n";
}
else {
if (node.second.second == end) {
return d;
}
//cout << "Minimum distance for " << node.second.second << " is " << d << "\n";
}
processed[node.second.first][node.second.second] = true;
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
vi tmp;
r = R, c = C;
if (C != 1) sub1 = false;
if (max(R, C) > 20) {
sub2 = false;
}
if (C == 2) {
sub3 = true;
sub2 = false;
}
if (sub2) {
mindists.resize(C, vi(C, 1000000000));
}
rep(i, R) {
tmp.clear();
rep(j, C - 1) {
tmp.pb(H[i][j]);
}
h.pb(tmp);
}
rep(i, R-1) {
tmp.clear();
rep(j, C) {
tmp.pb(V[i][j]);
if (sub1) totw += V[i][j];
}
v.pb(tmp);
}
if (sub2) {
rep(i, c) {
processed.clear();
processed.resize(R, vb(C, false));
sub2calc(i);
}
}
if (sub3) {
s3dp.resize(r, v2i(c, vi(2)));
rep(i, r) {
s3update(i);
//cout << "Initial dp update " << i << "\n";
}
}
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
if (sub3) {
rept(i, P, r) {
s3update(i);
//cout << "dp update " << i << "\n";
}
}
}
void changeV(int P, int Q, int W) {
totw += W - v[P][Q];
v[P][Q] = W;
if (sub3) {
rept(i, P+1, r) {
s3update(i);
//cout << "dp update " << i << "\n";
}
}
}
int escape(int V1, int V2) {
if (sub1) {
return totw;
}
if (sub2) {
return mindists[V1][V2];
}
if (sub3) {
return s3dp[r - 1][V2][V1];
}
if (sub4) {
processed.clear();
processed.resize(r, vb(c, false));
mindist4(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]
15 | int res;
| ^~~
wombats.cpp: In function 'void s3update(int)':
wombats.cpp:41:9: warning: unused variable 's' [-Wunused-variable]
41 | int s, c;
| ^
wombats.cpp:41:12: warning: unused variable 'c' [-Wunused-variable]
41 | int s, c;
| ^
wombats.cpp: In function 'int mindist4(int, int)':
wombats.cpp:134:1: warning: control reaches end of non-void function [-Wreturn-type]
134 | }
| ^
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:218:1: warning: control reaches end of non-void function [-Wreturn-type]
218 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4636 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4796 KB |
Output is correct |
| 3 |
Correct |
51 ms |
7480 KB |
Output is correct |
| 4 |
Correct |
4 ms |
4636 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4680 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
3 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
3 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
352 KB |
Output is correct |
| 8 |
Correct |
2 ms |
344 KB |
Output is correct |
| 9 |
Correct |
3 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
348 KB |
Output is correct |
| 11 |
Correct |
41 ms |
2740 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1112 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9564 KB |
Output is correct |
| 2 |
Correct |
29 ms |
9564 KB |
Output is correct |
| 3 |
Correct |
16 ms |
9644 KB |
Output is correct |
| 4 |
Correct |
49 ms |
10808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1112 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1116 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
