oj.uz

Submission #104939

# Submission time Handle Problem Language Result Execution time Memory
104939 2019-04-09T21:08:45 Z Noam527 Wall (CEOI14_wall) C++17
100 / 100
 703 ms 132400 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19840 KB Output is correct
2 Correct 20 ms 19712 KB Output is correct
3 Correct 19 ms 19712 KB Output is correct
4 Correct 19 ms 19712 KB Output is correct
5 Correct 20 ms 19712 KB Output is correct
6 Correct 24 ms 20608 KB Output is correct
7 Correct 23 ms 20480 KB Output is correct
8 Correct 23 ms 20500 KB Output is correct
9 Correct 22 ms 20348 KB Output is correct
10 Correct 24 ms 20608 KB Output is correct
11 Correct 22 ms 20736 KB Output is correct
12 Correct 23 ms 20992 KB Output is correct
13 Correct 24 ms 21248 KB Output is correct
14 Correct 23 ms 21112 KB Output is correct
15 Correct 21 ms 20992 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21104 KB Output is correct
2 Correct 23 ms 21248 KB Output is correct
3 Correct 24 ms 21120 KB Output is correct
4 Correct 23 ms 21248 KB Output is correct
5 Correct 23 ms 21120 KB Output is correct
6 Correct 23 ms 21112 KB Output is correct
7 Correct 24 ms 21260 KB Output is correct
8 Correct 25 ms 21112 KB Output is correct
9 Correct 24 ms 21120 KB Output is correct
10 Correct 28 ms 21376 KB Output is correct
11 Correct 25 ms 21248 KB Output is correct
12 Correct 24 ms 21120 KB Output is correct
13 Correct 24 ms 21180 KB Output is correct
14 Correct 24 ms 21120 KB Output is correct
15 Correct 26 ms 21240 KB Output is correct
16 Correct 27 ms 21300 KB Output is correct
17 Correct 25 ms 21120 KB Output is correct
18 Correct 24 ms 21120 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 46556 KB Output is correct
2 Correct 124 ms 42744 KB Output is correct
3 Correct 146 ms 44440 KB Output is correct
4 Correct 158 ms 44684 KB Output is correct
5 Correct 224 ms 75088 KB Output is correct
6 Correct 161 ms 46436 KB Output is correct
7 Correct 320 ms 80948 KB Output is correct
8 Correct 317 ms 79608 KB Output is correct
9 Correct 291 ms 79020 KB Output is correct
10 Correct 374 ms 82836 KB Output is correct
11 Correct 386 ms 86452 KB Output is correct
12 Correct 109 ms 45788 KB Output is correct
13 Correct 294 ms 77060 KB Output is correct
14 Correct 398 ms 110064 KB Output is correct
15 Correct 511 ms 118736 KB Output is correct
16 Correct 511 ms 119868 KB Output is correct
17 Correct 702 ms 126348 KB Output is correct
18 Correct 703 ms 132400 KB Output is correct
19 Correct 646 ms 121628 KB Output is correct
20 Correct 523 ms 118544 KB Output is correct