Submission #624334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
624334	2022-08-07T23:00:12 Z	GusterGoose27	Wall (CEOI14_wall)	C++11	100 / 100	769 ms	81568 KB

wall

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> edge;

const int MAXN = 405;
const ll inf = 1e18;
ll dist[MAXN][MAXN];
int n, m;
pii par[MAXN][MAXN];
int path_mask[MAXN][MAXN]; // right, up, left, down
vector<edge> edges[MAXN][MAXN]; // node, weight
bool village[MAXN][MAXN];
vector<pii> village_list;
bool pruned[MAXN][MAXN];
vector<pii> expans_graph[4*MAXN*MAXN];
ll dist2[4*MAXN*MAXN];

struct comp {
	bool operator()(const pii &a, const pii &b) {
		return (dist[a.first][a.second] == dist[b.first][b.second]) ? (a < b) : (dist[a.first][a.second] < dist[b.first][b.second]);
	}
};

struct comp2 {
	bool operator()(const int &a, const int &b) {
		return (dist2[a] == dist2[b]) ? (a < b) : (dist2[a] < dist2[b]);
	}
};

int hsh(int i, int j, int d) {
	return 4*(i*(m+1)+j)+d;
}

void dijkstra() {
	set<pii, comp> pq;
	dist[0][0] = 0;
	pq.insert(pii(0, 0));
	while (!pq.empty()) {
		pii cur = *(pq.begin());
		pq.erase(cur);
		ll curdist = dist[cur.first][cur.second];
		for (edge e: edges[cur.first][cur.second]) {
			pii next = e.first;
			if (curdist + e.second < dist[next.first][next.second]) {
				pq.erase(next);
				dist[next.first][next.second] = curdist + e.second;
				par[next.first][next.second] = cur;
				pq.insert(next);
			}
		}
	}
}

void dijkstra2() {
	set<int, comp2> pq;
	dist2[hsh(0, 0, 0)] = 0;
	pq.insert(0);
	while (!pq.empty()) {
		int cur = *(pq.begin());
		pq.erase(cur);
		for (pii p: expans_graph[cur]) {
			int next = p.first;
			if (dist2[cur]+p.second < dist2[next]) {
				pq.erase(next);
				dist2[next] = dist2[cur]+p.second;
				pq.insert(next);
			}
		}
	}
}

void prune(pii cur) {
	if (pruned[cur.first][cur.second]) return;
	pruned[cur.first][cur.second] = 1;
	pii parent = par[cur.first][cur.second];
	if (parent.first == cur.first && parent.second == cur.second-1) { // left
		path_mask[parent.first][parent.second] |= 1;
		path_mask[cur.first][cur.second] |= 4;
	}
	if (parent.first == cur.first && parent.second == cur.second+1) { // right
		path_mask[parent.first][parent.second] |= 4;
		path_mask[cur.first][cur.second] |= 1;
	}
	if (parent.first == cur.first-1 && parent.second == cur.second) { // up
		path_mask[parent.first][parent.second] |= 8;
		path_mask[cur.first][cur.second] |= 2;
	}
	if (parent.first == cur.first+1 && parent.second == cur.second) { // down
		path_mask[parent.first][parent.second] |= 2;
		path_mask[cur.first][cur.second] |= 8;
	}
	prune(parent);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i <= n; i++) fill(dist[i], dist[i]+m+1, inf);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> village[i][j];
			if (village[i][j]) village_list.push_back(pii(i, j));
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= m; j++) {
			int v; cin >> v;
			edges[i][j].push_back(edge(pii(i+1, j), v));
			edges[i+1][j].push_back(edge(pii(i, j), v));
			int hsh1 = hsh(i, j, 3);
			int hsh2 = hsh(i+1, j, 1);
			expans_graph[hsh(i, j, 3)].push_back(pii(hsh(i+1, j, 0), v));
			expans_graph[hsh(i, j, 2)].push_back(pii(hsh(i+1, j, 1), v));
			expans_graph[hsh(i+1, j, 0)].push_back(pii(hsh(i, j, 3), v));
			expans_graph[hsh(i+1, j, 1)].push_back(pii(hsh(i, j, 2), v));
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			int v; cin >> v;
			edges[i][j].push_back(edge(pii(i, j+1), v));
			edges[i][j+1].push_back(edge(pii(i, j), v));
			expans_graph[hsh(i, j, 0)].push_back(pii(hsh(i, j+1, 1), v));
			expans_graph[hsh(i, j, 3)].push_back(pii(hsh(i, j+1, 2), v));
			expans_graph[hsh(i, j+1, 1)].push_back(pii(hsh(i, j, 0), v));
			expans_graph[hsh(i, j+1, 2)].push_back(pii(hsh(i, j, 3), v));
		}
	}
	dijkstra();
	pruned[0][0] = 1;
	for (pii p: village_list) {
		prune(p);
		path_mask[p.first][p.second] |= 9;
		path_mask[p.first+1][p.second] |= 3;
		path_mask[p.first][p.second+1] |= 12;
		path_mask[p.first+1][p.second+1] |= 6;
	}
	// node numbering scheme: row, column index*4 + direction index. right-up, up-left, left-down, down-right for directions
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i == 0 && j == 0) continue;
			if (!(path_mask[i][j] & 1)) {
				expans_graph[hsh(i, j, 0)].push_back(pii(hsh(i, j, 3), 0));
				expans_graph[hsh(i, j, 3)].push_back(pii(hsh(i, j, 0), 0));
			}
			if (!(path_mask[i][j] & 2)) {
				expans_graph[hsh(i, j, 0)].push_back(pii(hsh(i, j, 1), 0));
				expans_graph[hsh(i, j, 1)].push_back(pii(hsh(i, j, 0), 0));
			}
			if (!(path_mask[i][j] & 4)) {
				expans_graph[hsh(i, j, 1)].push_back(pii(hsh(i, j, 2), 0));
				expans_graph[hsh(i, j, 2)].push_back(pii(hsh(i, j, 1), 0));
			}
			if (!(path_mask[i][j] & 8)) {
				expans_graph[hsh(i, j, 2)].push_back(pii(hsh(i, j, 3), 0));
				expans_graph[hsh(i, j, 3)].push_back(pii(hsh(i, j, 2), 0));
			}
		}
	}
	fill(dist2, dist2+4*MAXN*MAXN, inf);
	dijkstra2();
	cout << dist2[hsh(0, 0, 2)] << "\n";
}

Compilation message

wall.cpp: In function 'int main()':
wall.cpp:114:8: warning: unused variable 'hsh1' [-Wunused-variable]
  114 |    int hsh1 = hsh(i, j, 3);
      |        ^~~~
wall.cpp:115:8: warning: unused variable 'hsh2' [-Wunused-variable]
  115 |    int hsh2 = hsh(i+1, j, 1);
      |        ^~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	24788 KB	Output is correct
2	Correct	12 ms	24832 KB	Output is correct
3	Correct	11 ms	24820 KB	Output is correct
4	Correct	12 ms	24856 KB	Output is correct
5	Correct	12 ms	24860 KB	Output is correct
6	Correct	14 ms	25172 KB	Output is correct
7	Correct	14 ms	25172 KB	Output is correct
8	Correct	13 ms	25172 KB	Output is correct
9	Correct	13 ms	25044 KB	Output is correct
10	Correct	16 ms	25120 KB	Output is correct
11	Correct	18 ms	25412 KB	Output is correct
12	Correct	16 ms	25432 KB	Output is correct
13	Correct	16 ms	25508 KB	Output is correct
14	Correct	15 ms	25540 KB	Output is correct
15	Correct	15 ms	25252 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	25556 KB	Output is correct
2	Correct	15 ms	25512 KB	Output is correct
3	Correct	17 ms	25504 KB	Output is correct
4	Correct	18 ms	25548 KB	Output is correct
5	Correct	16 ms	25556 KB	Output is correct
6	Correct	16 ms	25556 KB	Output is correct
7	Correct	16 ms	25556 KB	Output is correct
8	Correct	17 ms	25508 KB	Output is correct
9	Correct	18 ms	25556 KB	Output is correct
10	Correct	17 ms	25616 KB	Output is correct
11	Correct	16 ms	25484 KB	Output is correct
12	Correct	16 ms	25556 KB	Output is correct
13	Correct	15 ms	25556 KB	Output is correct
14	Correct	16 ms	25512 KB	Output is correct
15	Correct	16 ms	25568 KB	Output is correct
16	Correct	16 ms	25508 KB	Output is correct
17	Correct	16 ms	25556 KB	Output is correct
18	Correct	17 ms	25504 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	152 ms	37264 KB	Output is correct
2	Correct	103 ms	35528 KB	Output is correct
3	Correct	105 ms	36272 KB	Output is correct
4	Correct	136 ms	37240 KB	Output is correct
5	Correct	167 ms	51788 KB	Output is correct
6	Correct	116 ms	37324 KB	Output is correct
7	Correct	266 ms	53436 KB	Output is correct
8	Correct	284 ms	52896 KB	Output is correct
9	Correct	252 ms	52812 KB	Output is correct
10	Correct	383 ms	55376 KB	Output is correct
11	Correct	407 ms	57976 KB	Output is correct
12	Correct	86 ms	37144 KB	Output is correct
13	Correct	272 ms	51820 KB	Output is correct
14	Correct	330 ms	68172 KB	Output is correct
15	Correct	461 ms	71768 KB	Output is correct
16	Correct	499 ms	72664 KB	Output is correct
17	Correct	682 ms	76288 KB	Output is correct
18	Correct	769 ms	81568 KB	Output is correct
19	Correct	598 ms	73436 KB	Output is correct
20	Correct	465 ms	72140 KB	Output is correct