Submission #104939

#	Time	Username	Problem	Language	Result	Execution time	Memory
104939		Noam527	Wall (CEOI14_wall)	C++17	100 / 100	703 ms	132400 KiB

wall

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct edge {
	int x, y, r;
	ll w;
	edge() {}
	edge(int xx, int yy, int rr, ll ww) : x(xx), y(yy), r(rr), w(ww) {}
	bool operator < (const edge &a) const {
		return w > a.w;
	}
};

int n, m;
vector<pair<int, int>> tar;
int V[404][404], H[404][404];
vector<edge> g[404][404];

ll dg[404][404];
bool found[404][404] = {};
pair<int, int> back[404][404];
bool block[404][404][4] = {};
bool blocked[404][404] = {};

vector<edge> t[404][404][4];
ll dt[404][404][4];


void dijk1() {
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) dg[i][j] = inf;
	priority_queue<edge> Q;
	Q.push(edge(0, 0, -1, 0));
	while (Q.size()) {
		edge x = Q.top();
		Q.pop();
		if (found[x.x][x.y]) continue;
		found[x.x][x.y] = 1;
		for (const auto &i : g[x.x][x.y]) {
			if (x.w + i.w < dg[i.x][i.y]) {
				dg[i.x][i.y] = x.w + i.w;
				back[i.x][i.y] = { x.x, x.y };
				Q.push(edge(i.x, i.y, -1, x.w + i.w));
			}
		}
	}
}

void applyblock(pair<int, int> x, pair<int, int> y) {
	if (x > y) swap(x, y);
	if (OO) {
		cout << "applying block on\n";
		cout << x.first << " " << x.second << '\n';
		cout << "to\n";
		cout << y.first << " " << y.second << '\n';
	}
	if (x.second == y.second) block[x.first][x.second][3] = block[y.first][y.second][1] = 1;
	else block[x.first][x.second][0] = block[y.first][y.second][2] = 1;
}

ll dijk2() {
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < 4; k++)
		dt[i][j][k] = inf;
	dt[0][0][1] = -1; // block cycle vertex
	priority_queue<edge> Q;
	Q.push(edge(0, 0, 0, 0));
	while (Q.size()) {
		edge x = Q.top();
		Q.pop();
		if (dt[x.x][x.y][x.r] != inf) continue;
		if (OO) {
			cout << "determined " << x.x << " " << x.y << " " << x.r << " = " << x.w << '\n';
		}
		dt[x.x][x.y][x.r] = x.w;
		for (const auto &i : t[x.x][x.y][x.r]) {
			if (dt[i.x][i.y][i.r] > x.w + i.w) {
				Q.push(edge(i.x, i.y, i.r, x.w + i.w));
			}
		}
	}
	return dt[0][0][2];
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		int tmp;
		cin >> tmp;
		if (tmp) tar.emplace_back(i, j);
	}
	for (int i = 0; i < n; i++) for (int j = 0; j <= m; j++) cin >> V[i][j];
	for (int i = 0; i <= n; i++) for (int j = 0; j < m; j++) cin >> H[i][j];

	n++, m++;
	// make graph 1
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		if (j + 1 < m) g[i][j].push_back(edge(i, j + 1, -1, H[i][j]));
		if (j - 1 >= 0) g[i][j].push_back(edge(i, j - 1, -1, H[i][j - 1]));
		if (i - 1 >= 0) g[i][j].push_back(edge(i - 1, j, -1, V[i - 1][j]));
		if (i + 1 < n) g[i][j].push_back(edge(i + 1, j, -1, V[i][j]));
	}
	dijk1();
	// now block....smh. track first
	if (OO) cout << "now tracking\n";
	for (const auto &i : tar) {
		pair<int, int> pos = i;
		while ((pos.first > 0 || pos.second > 0) && !blocked[pos.first][pos.second]) {
			blocked[pos.first][pos.second] = 1;
			applyblock(back[pos.first][pos.second], pos);
			pos = back[pos.first][pos.second];
		}
	}
	// block around targets
	if (OO) cout << "now around\n";
	for (const auto &i : tar) {
		pair<int, int> pos = i;
		applyblock(pos, { pos.first, pos.second + 1 });
		applyblock(pos, { pos.first + 1, pos.second });
		applyblock({ pos.first + 1, pos.second + 1 }, { pos.first, pos.second + 1 });
		applyblock({ pos.first + 1, pos.second + 1 }, { pos.first + 1, pos.second });
	}
	if (OO) {
		cout << "now some tests!!\n";
		cout << block[0][1][2] << '\n';
	}
	// make graph 2
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		// 0
		if (i - 1 >= 0) t[i][j][0].push_back(edge(i - 1, j, 3, V[i - 1][j]));
		if (j + 1 < m) t[i][j][0].push_back(edge(i, j + 1, 1, H[i][j]));
		if (!block[i][j][0]) t[i][j][0].push_back(edge(i, j, 3, 0));
		if (!block[i][j][1]) t[i][j][0].push_back(edge(i, j, 1, 0));
		// 1
		if (i - 1 >= 0) t[i][j][1].push_back(edge(i - 1, j, 2, V[i - 1][j]));
		if (j - 1 >= 0) t[i][j][1].push_back(edge(i, j - 1, 0, H[i][j - 1]));
		if (!block[i][j][2]) t[i][j][1].push_back(edge(i, j, 2, 0));
		if (!block[i][j][1]) t[i][j][1].push_back(edge(i, j, 0, 0));
		// 2
		if (i + 1 < n) t[i][j][2].push_back(edge(i + 1, j, 1, V[i][j]));
		if (j - 1 >= 0) t[i][j][2].push_back(edge(i, j - 1, 3, H[i][j - 1]));
		if (!block[i][j][2]) t[i][j][2].push_back(edge(i, j, 1, 0));
		if (!block[i][j][3]) t[i][j][2].push_back(edge(i, j, 3, 0));
		// 3
		if (i + 1 < n) t[i][j][3].push_back(edge(i + 1, j, 0, V[i][j]));
		if (j + 1 < m) t[i][j][3].push_back(edge(i, j + 1, 2, H[i][j]));
		if (!block[i][j][0]) t[i][j][3].push_back(edge(i, j, 0, 0));
		if (!block[i][j][3]) t[i][j][3].push_back(edge(i, j, 2, 0));
	}
	cout << dijk2() << '\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40