oj.uz

Submission #49878

# Submission time Handle Problem Language Result Execution time Memory
49878 2018-06-04T03:21:50 Z aome Wall (CEOI14_wall) C++17
100 / 100
 460 ms 22956 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 405;
const long long INF = 1e18;

struct State {
	long long v;
	int x, y, d;

	State (long long v, int x, int y, int d) :
		v(v), x(x), y(y), d(d) {}

	bool operator < (const State& rhs) const {
		return v > rhs.v;
	}
};

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

int n, m;
int cost[4][N][N];
bool a[N][N];
bool vis[N][N];
bool mark[4][N][N];
long long dis[N][N];
long long f[4][N][N];

void dijkstra() {
	for (int i = 1; i <= n + 1; ++i) {
		for (int j = 1; j <= m + 1; ++j) {
			dis[i][j] = INF;
		}
	}
	priority_queue<State> pq;
	pq.push(State(dis[1][1] = 0, 1, 1, 0));
	while (pq.size()) {
		long long v = pq.top().v;
		int x = pq.top().x, y = pq.top().y;
		pq.pop();
		if (v != dis[x][y]) continue;
		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 1 || nx > n + 1 || ny < 1 || ny > m + 1) continue;
			if (dis[nx][ny] > v + cost[i][x][y]) {
				dis[nx][ny] = v + cost[i][x][y];
				pq.push(State(dis[nx][ny], nx, ny, 0));
			}
		}
	}
}

void rec(int x, int y) {
	if (x == 1 && y == 1 || vis[x][y]) return;
	vis[x][y] = 1;
	for (int i = 0; i < 4; ++i) {
		int nx = x - dx[i], ny = y - dy[i];
		if (nx < 1 || nx > n + 1 || ny < 1 || ny > m + 1) continue;
		if (dis[nx][ny] + cost[i][nx][ny] == dis[x][y]) {
			mark[i ^ 1][x][y] = mark[i][nx][ny] = 1, rec(nx, ny); return;
		}
	}
}

void solve() {
	for (int i = 1; i <= n + 1; ++i) {
		for (int j = 1; j <= m + 1; ++j) {
			for (int k = 0; k < 4; ++k) {
				f[k][i][j] = INF;
			}
		}
	}
	priority_queue<State> pq;
	pq.push(State(f[1][1][2] = cost[1][1][1], 1, 2, 1));
	while (pq.size()) {
		long long v = pq.top().v;
		int x = pq.top().x, y = pq.top().y, d = pq.top().d;
		pq.pop();
		if (v != f[d][x][y]) continue;

		if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
			if (f[0][x][y - 1] > v + cost[0][x][y]) {
				f[0][x][y - 1] = v + cost[0][x][y];
				pq.push(State(f[0][x][y - 1], x, y - 1, 0));
			}
		}

		if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
			if (f[1][x][y + 1] > v + cost[1][x][y]) {
				f[1][x][y + 1] = v + cost[1][x][y];
				pq.push(State(f[1][x][y + 1], x, y + 1, 1));
			}
		}

		if ( !(d == 0 && (mark[0][x][y] || mark[3][x][y]) || d == 2 && mark[0][x][y] || d == 3 || x == 1) ) {
			if (f[2][x - 1][y] > v + cost[2][x][y]) {
				f[2][x - 1][y] = v + cost[2][x][y];
				pq.push(State(f[2][x - 1][y], x - 1, y, 2));
			}
		}

		if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
			if (f[3][x + 1][y] > v + cost[3][x][y]) {
				f[3][x + 1][y] = v + cost[3][x][y];
				pq.push(State(f[3][x + 1][y], x + 1, y, 3));
			}
		}

		// if (d == 0) {
		// 	for (auto i : G[x][y]) {
		// 		if (i.d == 1) continue;
		// 		if (i.d == 0 && mark[3][x][y]) continue;
		// 		if (i.d == 2 && (mark[0][x][y] || mark[3][x][y])) continue;
		// 		if (f[i.d][i.x][i.y] > v + i.w) {
		// 			f[i.d][i.x][i.y] = v + i.w;
		// 			pq.push(State(v + i.w, i.x, i.y, i.d));
		// 		}
		// 	}
		// }
		// if (d == 1) {
		// 	for (auto i : G[x][y]) {
		// 		if (i.d == 0) continue;
		// 		if (i.d == 1 && mark[2][x][y]) continue;
		// 		if (i.d == 3 && (mark[1][x][y] || mark[2][x][y])) continue;
		// 		if (f[i.d][i.x][i.y] > v + i.w) {
		// 			f[i.d][i.x][i.y] = v + i.w;
		// 			pq.push(State(v + i.w, i.x, i.y, i.d));
		// 		}
		// 	}
		// }
		// if (d == 2) {
		// 	for (auto i : G[x][y]) {
		// 		if (i.d == 3) continue;
		// 		if (i.d == 2 && mark[0][x][y]) continue;
		// 		if (i.d == 1 && (mark[0][x][y] || mark[2][x][y])) continue;
		// 		if (f[i.d][i.x][i.y] > v + i.w) {
		// 			f[i.d][i.x][i.y] = v + i.w;
		// 			pq.push(State(v + i.w, i.x, i.y, i.d));
		// 		}
		// 	}
		// }
		// if (d == 3) {
		// 	for (auto i : G[x][y]) {
		// 		if (i.d == 2) continue;
		// 		if (i.d == 3 && mark[1][x][y]) continue;
		// 		if (i.d == 0 && (mark[1][x][y] || mark[3][x][y])) continue;
		// 		if (f[i.d][i.x][i.y] > v + i.w) {
		// 			f[i.d][i.x][i.y] = v + i.w;
		// 			pq.push(State(v + i.w, i.x, i.y, i.d));
		// 		}
		// 	}
		// }
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
			if (a[i][j]) {
				mark[0][i][j + 1] = mark[0][i + 1][j + 1] = 1;
				mark[1][i][j] = mark[1][i + 1][j] = 1;
				mark[2][i + 1][j] = mark[2][i + 1][j + 1] = 1;
				mark[3][i][j] = mark[3][i][j + 1] = 1;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m + 1; ++j) {
			int w; cin >> w;
			cost[3][i][j] = cost[2][i + 1][j] = w;
		}
	} 
	for (int i = 1; i <= n + 1; ++i) {
		for (int j = 1; j <= m; ++j) {
			int w; cin >> w;
			cost[1][i][j] = cost[0][i][j + 1] = w;
		}
	}
	dijkstra();
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (a[i][j]) rec(i, j);
		}
	}
	// for (int i = 1; i <= n + 1; ++i) {
	// 	for (int j = 1; j <= m + 1; ++j) {
	// 		for (int k = 1; k < 4; k += 2) {
	// 			if (mark[k][i][j]) {
	// 				cout << i << ' ' << j << ' ' << k << '\n';
	// 			}
	// 		}
	// 	}
	// }
	solve();
	cout << f[2][1][1];
}

Compilation message

wall.cpp: In function 'void rec(int, int)':
wall.cpp:56:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  if (x == 1 && y == 1 || vis[x][y]) return;
      ~~~~~~~^~~~~~~~~
wall.cpp: In function 'void solve()':
wall.cpp:83:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
          ~~~~~~~^~~~~~~~~~~~~~~~
wall.cpp:83:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:90:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
                    ~~~~~~~^~~~~~~~~~~~~~~~
wall.cpp:90:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:97:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 0 && (mark[0][x][y] || mark[3][x][y]) || d == 2 && mark[0][x][y] || d == 3 || x == 1) ) {
          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:104:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:104:73: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
                                                                  ~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 3 ms 816 KB Output is correct
5 Correct 3 ms 816 KB Output is correct
6 Correct 4 ms 1340 KB Output is correct
7 Correct 5 ms 1340 KB Output is correct
8 Correct 4 ms 1340 KB Output is correct
9 Correct 4 ms 1340 KB Output is correct
10 Correct 3 ms 1400 KB Output is correct
11 Correct 4 ms 1528 KB Output is correct
12 Correct 5 ms 1656 KB Output is correct
13 Correct 4 ms 1656 KB Output is correct
14 Correct 4 ms 1656 KB Output is correct
15 Correct 4 ms 1656 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1660 KB Output is correct
2 Correct 6 ms 1664 KB Output is correct
3 Correct 5 ms 1664 KB Output is correct
4 Correct 4 ms 1788 KB Output is correct
5 Correct 5 ms 1788 KB Output is correct
6 Correct 5 ms 1788 KB Output is correct
7 Correct 6 ms 1788 KB Output is correct
8 Correct 5 ms 1788 KB Output is correct
9 Correct 5 ms 1788 KB Output is correct
10 Correct 5 ms 1788 KB Output is correct
11 Correct 4 ms 1788 KB Output is correct
12 Correct 4 ms 1788 KB Output is correct
13 Correct 4 ms 1788 KB Output is correct
14 Correct 5 ms 1788 KB Output is correct
15 Correct 5 ms 1788 KB Output is correct
16 Correct 4 ms 1788 KB Output is correct
17 Correct 4 ms 1788 KB Output is correct
18 Correct 5 ms 1788 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5988 KB Output is correct
2 Correct 46 ms 5988 KB Output is correct
3 Correct 54 ms 5988 KB Output is correct
4 Correct 67 ms 7480 KB Output is correct
5 Correct 82 ms 8160 KB Output is correct
6 Correct 61 ms 8160 KB Output is correct
7 Correct 149 ms 8828 KB Output is correct
8 Correct 119 ms 8828 KB Output is correct
9 Correct 117 ms 8828 KB Output is correct
10 Correct 198 ms 11176 KB Output is correct
11 Correct 234 ms 14528 KB Output is correct
12 Correct 39 ms 14528 KB Output is correct
13 Correct 137 ms 14528 KB Output is correct
14 Correct 174 ms 14528 KB Output is correct
15 Correct 206 ms 14528 KB Output is correct
16 Correct 232 ms 14528 KB Output is correct
17 Correct 357 ms 16832 KB Output is correct
18 Correct 460 ms 22956 KB Output is correct
19 Correct 331 ms 22956 KB Output is correct
20 Correct 256 ms 22956 KB Output is correct