Submission #624334

#	Time	Username	Problem	Language	Result	Execution time	Memory
624334		GusterGoose27	Wall (CEOI14_wall)	C++11	100 / 100	769 ms	81568 KiB

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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40